AcWing 1209. 带分数
原题链接
简单
作者:
小王子_19
,
2024-04-08 21:25:52
,
所有人可见
,
阅读 1
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n;
bool st[20], backup[20];
int cnt;
bool check(int a, int c)
{
int b = (n - a) * c;
if (!a || !b || !c) return false;
memcpy(backup, st, sizeof st);
while (b)
{
int t = b % 10;
if (!t) return false;
if (backup[t]) return false;
else backup[t] = true;
b /= 10;
}
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)) cnt ++ ;
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 << cnt << endl;
return 0;
}