第四届真题-带分数

解题思路:

注意事项:

参考代码:

/*暴力思路：
1.枚举全排列
2.枚举a,b,c的每一位数，枚举其中两个即可。可以使用高中排列知识，在9位数中找2个空隙放隔板
3.判断等式是否成立*/
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int n;
bool st[N];
bool backup[N];
int ans;

bool check(int a, int c)
{
    long long b = n *(long long) c - a * c;
    if (!a || !b || !c)return false;
    memcpy(backup, st, sizeof st);

    while (b)
    {
        int x = b % 10;
        b /= 10;
        if (!x || backup[x])return false;
        backup[x] = true;
    }
    for (int i = 1; i <= 9; i++)
        if (!backup[i])
            return false;
    return true;
}
void dfs_c(int u, int a, int c)
{
    if (u >9)return;//位数足够
    if (check(a, c))ans++;//满足条件，c*n=a*c+b，ans+1

    for (int i = 1; i <= 9; i++)
    {
        if (!st[i])
        {
            st[i] = true;
            dfs_c(u + 1, a, c * 10 + i);
            st[i] = false;//恢复现场
        }
    }
}
void dfs_a(int u, int a)
{
    if (a >= n)return;
    if (a) dfs_c(u, a, 0);//对于每个枚举的a，都枚举一下c。

    for (int i = 1; i <= 9; i++)
    {
        if (!st[i])
        {
            st[i] = true;
            dfs_a(u + 1, a * 10 + i);
            st[i] = false;//恢复现场
        }
    }
}
int main()
{
  
    cin >> n;
    dfs_a(0, 0);//第一个参数为当前已经用了多少个数字，0表示最开始一个数字都没有
    cout << ans << endl;
    return 0;
}