1209.带分数

注意点:check函数的编写要考虑全面 为0或者重复使用

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

int cp[10],status[10];
int ans=0;

int n;

bool check(int a,int c)
{
    int b = n * c - a * c;
    if(!a||!b||!c) return false;
    memcpy(cp,status,sizeof status);
    //memcpy在cstring头文件中
    //copy了一个新数组cp,其中 cp[1~9]就存储
    //之前a与c所用数字情况,1代表用了,现在判断b中的
    while(b)
    {
        int t = b % 10; //找当前的个位数
        b /= 10;        //b/10 寻找下一个高位数
        if(!t||cp[t]) return false; //存在a与c中已经用过的数字or使用了数字0则b匹配失败
        cp[t] = 1;  //令此数字为1代表使用
    }
    for(int i=1;i <= 9; i ++)
    {
        if(!cp[i]) return false;    //存在未用的则b匹配失败
    }
    return true;
}


void dfs_c(int u,int a,int c)
{
    if(u == 10) return;     //到达边界
    if(check(a,c)) ans++;   //检查是否符合

    for(int i = 1; i <= 9; i ++)
        if(!status[i])
        {
            status[i]=1;
            dfs_c(u+1,a,c*10+i);
            status[i]=0;
        }
}


void dfs_a(int u,int a)
{
    if(a >= n) return;
    if(a) dfs_c(u,a,0);     //a不能为0

    for(int i = 1; i <= 9; i ++)
    {
        if(!status[i])
        {
            status[i]=1;
            dfs_a(u+1,a*10+i);

            status[i]=0;    //必须进行恢复,a可以不选此数字
        }
    }
}

int main()
{
    cin >> n;
    dfs_a(0,0);//前者代表使用了多少个数字(用于寻找边界),后者代表a的数值
    cout << ans;
    return 0;
}