题目描述
100可以表示为带分数的形式:100=3+69258714
还可以表示为:100=82+3546197
注意特征:带分数中,数字 1∼9分别出现且只出现一次(不包含 0
)。
类似这样的带分数,100有 11种表示法。
样例
输入样例1:
100
输出样例1:
11
输入样例2:
105
输出样例2:
6
C++ 代码
#include<algorithm>
#include<cstdio>
#include<iostream>
using namespace std;
const int N=10;
int n;
int path[N];
bool st[N];
int cnt;
int cul(int l,int r)
{
int res=0;
for(int i=l;i<=r;i++)
res=res*10+path[i];
return res;
}
void dfs(int u)
{
if(u>9)
{
for(int i=1;i<8;i++)
for(int j=i+1;j<=9;j++)
{
int a=cul(1,i);
int b=cul(i+1,j);
int c=cul(j+1,9);
if(a*c+b==n*c)
cnt++;
}
return;
}
for(int i=1;i<=9;i++)
if(!st[i])
{ path[u]=i;
st[i]=true;
dfs(u+1);
st[i]=false;
}
}
int main()
{
cin>>n;
dfs(1);
cout<<cnt<<endl;
return 0;
}