800+ ms 的代码

思路：
c * n - c * a = b;
判断 b 是否符合条件

时间复杂度

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

int n, m, res = 0;
bool st[10];

bool judge(int b) // 判断b是否满足条件
{
    bool temp[10];
    memcpy(temp, st, sizeof st);
    while(b)
    {
        if(b % 10 == 0 || temp[b % 10]) return false;   // b中含有0，或者存在已经出现的数字代表不满足
        temp[b % 10] = true, b /= 10;
    }
    for(int i = 1; i <= 9; i++) // 没有将0~9数字全部囊括，不满足
        if(!temp[i]) return false;
    return true;
}

void dfs1(int c, const int a){  // 遍历 c 可能的值
    if(c && c * n - c * a <= 0) return; // 这行可以不加，的理论上永远不会执行，但是去掉反而慢了(1000+)，可能巧合吧，大家也可以一起讨论
    if(judge(c * n - c * a)) res++;

    for(int i = 1; i <= 9; i ++){
        if(!st[i]){
            st[i] = true;
            dfs1(c * 10 + i, a);
            st[i] = false;
        }
    }
}

void dfs(int a){    // 遍历 a 可能的值
    if(a >= n) return; // a >= n 时，b定为负数，不满足要求，剪枝。 
    if(a) dfs1(0, a);

    for(int i = 1; i <= 9; i ++){
        if(!st[i]){
            st[i] = true;
            dfs(a * 10 + i);
            st[i] = false;
        }
    }
}

int main()
{
    cin >> n;
    dfs(0);
    printf("%d\n", res);
    return 0;
}