AcWing 1209. 带分数
原题链接
简单
C++ 代码
#include<bits/stdc++.h>
using namespace std;
//注意到分数处理比较麻烦,且这样很难利用n
//若原拆分式为n=a+b/c,可对式子两边同时乘上c,即n*c=a*c+b,好处是只用枚举a和c,而b可以直接算出来
//总体思路:先搜索a,再搜索c
int n,ans;
bool use[20];//表示已经用过哪些数字,注意这个use,cpy数组要稍微开大一点,不然有个数据过不了,我也不知道为啥
bool cpy[20];//use数组的副本
bool check(int a,int c){
int b=n*c-a*c;
if(!a||!b||!c)return false;
memcpy(cpy,use,sizeof use);//复制一下use数组防止改变其值
while(b){//看b中用到哪些数字
int k=b%10;
if(!k||cpy[k])return false;//如果出现数字0或者这个数字已经被使用过,失败
cpy[k]=1;
b/=10;
}
for(int i=1;i<=9;i++)
if(!cpy[i])
return false;//还有数字没用过,失败
return true;
}
void dfs_c(int u,int a,int c){//u表示已经用了几个数,a表示a的值,c表示当前c的值
if(u>=9)return;//数字都用完了,直接退出
if(check(a,c))ans++;//满足条件答案++
for(int i=1;i<=9;i++){
if(!use[i]){
use[i]=1;
dfs_c(u+1,a,10*c+i);
use[i]=0;
}
}
return;
}
void dfs_a(int u,int a){//u表示已经用了几个数,a表示当前a的值
if(a>=n)return;//a显然不能比n还大
if(a)dfs_c(u,a,0);//a满足条件就继续搜c
for(int i=1;i<=9;i++){
if(!use[i]){
use[i]=1;//标记这个数用过了
dfs_a(u+1,10*a+i);//搜下一层
use[i]=0;//回溯
}
}
return;
}
int main(){
cin>>n;
dfs_a(0,0);//搜索a
cout<<ans<<endl;
return 0;
}