算法
本质是求解1~9
的全排列,并对每组全排列分成三份,也就是三个数a,b,c
,判断是否有n = a+b/c
的值,如果满足就++
。由于整除运算会有小数点,所以我们可以考虑将公式进行变形,即n*c = a*c + b
,满足这个式子等价与题目要求的式子。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 11;
int n,ans;
int num[N];
bool st[N];
int cal(int l,int r)
{
int sum = 0;
for(int i=l;i<=r;i++)
sum = sum*10+num[i];
return sum;
}
void dfs(int u)
{
if(u>=10)
{
for(int j=2;j<9;j++)
for(int k=j+1;k<10;k++)
{
int a=cal(1,j-1),b=cal(j,k-1),c=cal(k,9);
if(a*c+b==n*c) ans++;
}
return ;
}
for(int i=1;i<10;i++)
{
if(!st[i])
{
st[i] = true;
num[u] = i;
dfs(u+1);
st[i] = false;
}
}
}
int main()
{
cin>>n;
dfs(1);
cout<<ans;
return 0;
}