【C++】带分数

100 可以表示为带分数的形式：100= 3 + 69258/714

还可以表示为：100=82+3546/197

注意特征：带分数中，数字 1∼9分别出现且只出现一次（不包含 0）。

类似这样的带分数，100有 11种表示法。
输入格式

一个正整数。
输出格式

输出输入数字用数码 1∼9不重复不遗漏地组成带分数表示的全部种数。
数据范围
1≤N<106
输入样例1：

100

输出样例1：

11

输入样例2：

105

输出样例2：

6

#include
#include
#include
using namespace std;

const int N = 20;
int n;
int ans; // 方案数
bool st[N],backup[N];

bool check(int a ,int c){
    int b = n * c - a * c;
    //都不能为0
    if(!a || !b || !c){
        return false;
    }
    
    //判断b的数字有没有重，且a，b，c为1-9
    memcpy(backup,st,sizeof st);
    
    while (b){
        int gewei  = b % 10;
        b /= 10; //删掉个位
        if (!gewei || backup[gewei] ){
            return false;
        }
        backup[gewei] = 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 == n){
        //已经用完了每个数字
        return;
    }
    if(check(a,c)){
        ans ++;
    }
    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){ //u表示当前已经用了几位数字
    //边界
    if(a >= n){
        //无解
        return;
    }
    dfs_c(u,a,0);
    
    //当前位
    for(int i = 1;i <= 9;i ++){
        //当前这位上这个数没用过
        if(!st[i]){
            st[i] = true;
            dfs_a(u + 1,a * 10 + i); //乘以10加上那个数，如：如何把12变成123
            //恢复现场
            st[i] = false;
        }
    }
}


int main(){
    cin >> n;
    //当前用了多少个数字
    dfs_a(0,0);
    
    cout << ans << endl;
    return 0;
}