题目描述
100 可以表示为带分数的形式:100=3+69258714
还可以表示为:100=82+3546197
注意特征:带分数中,数字 1∼9 分别出现且只出现一次(不包含 0)。
类似这样的带分数,100 有 11 种表示法。
样例
输入格式
一个正整数。
输出格式
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。
(暴力枚举)
C++ 代码
#include<iostream>
using namespace std;
const int N=10;
int m[N],used[N],n,res;
int cla(int l,int r)
{
int num = 0;
for(int i=l;i<=r;i++)
{
num=num*10+m[i];
}
return num;
}
void dfs(int u)
{
if(u>9)
{
for(int i=1;i<=6;i++)
{
for(int j=i+1;j<=9;j++)
{
int a=cla(1,i);
int b=cla(i+1,j);
int c=cla(j+1,9);
if(n*c==a*c+b)res++;
}
}
return;
}
for(int i=1;i<=9;i++)
if(!used[i])
{
used[i]=1;
m[u]=i;
dfs(u+1);
m[u]=0;
used[i]=0;
}
}
int main()
{
cin>>n;
dfs(1);
cout<<res;
return 0;
}