题目描述
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
这个题思路和大多数题解一样,先1到9全排列,再分三段,但做了一些优化。
1. N = A + B / C
可以写成
NC = NA + B,所以C小于A的部分可以减掉
2. 因为输入的N为正整数,所以B/C必然也是整数。所以有:
B的位数大于C的位数
B%C=0
这样 分段的时候就可以简化许多。
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
int n,ans;
int b[9];//全排列
int c[9];//判重
int A,B,C;//A+B/C
int f(int l,int r){//把位数转换为数字
int num=0;
for(int i=l;i<r;i++){
num*=10;
num+=b[i];
}
return num;
}
void dfs(int num){
if(num>9){
for(int i=1;i<=7;i++){
for(int j=1;j<=9-1-i;j++){
if(j>=9-i-j){
A=f(0,i);
B=f(i,i+j);
C=f(i+j,9);
int ck=B%C;//因为输入是整数,所以分数必须可以化成整数
if((ck==0)&&(A<n)){
if((B/C+A)==n){
ans++;
}
}
}
}
}
return;
}
for(int i=1;i<=9;i++){
if(c[i-1]==0){
b[num-1]=i;
c[i-1]=1;
dfs(num+1);
c[i-1]=0;
b[num-1]=0;
}
}
}
int main(){
cin>>n;
dfs(1);
cout<<ans<<endl;
return 0;
}