题目描述
100可以表示为带分数的形式:100=3+69258714
还可以表示为:100=82+3546197
注意特征:带分数中,数字 1∼9分别出现且只出现一次(不包含 0)。
类似这样的带分数,100有 11种表示法。
输入格式:一个正整数。
输出格式:输出输入数字用数码1∼9不重复不遗漏地组成带分数表示的全部种数。
数据范围:1≤N<106
样例
输入样例1:
100
输出样例1:
11
输入样例2:
105
输出样例2:
6
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=20;
int n;
bool st[N],backup[N];
int ans;
bool check(int a,int c){
int b=n*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==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){
if(a>=n)
return;
if(a)
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);
st[i]=false;
}
}
int main(){
cin>>n;
dfs_a(0,0);
cout<<ans<<endl;
return 0;
}