题目意思
-
$n = a +\frac{b}{c}$
-
a,b,c三个数恰好1~9每个数只出现一次
①大暴力 91445760
-
枚举全排列
-
枚举位数
-
判断等式是否成立
eee..91445760离超时不远了
②爆搜+剪枝
$n = a +\frac{b}{c}$ ->$nc = ac +b$->$b = nc - ac$
算$b$
枚举$a$,枚举$c$,在判断
$dfs$ _ $a, dfs $_$ c;$
$dfs$ _ $a的叶子上dfs$ _ $c$
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10;
int n;
bool st[N], backup[N];
int ans;
bool check(int a, int c)
{
long long b = n * (long long)c - a * c; // 公式
if (!a || !b || !c) return false; //不能取零
memcpy(backup, st, sizeof st);
while (b)
{
int x = b % 10; // 取个位
b /= 10; // 个位删掉
if (!x || backup[x]) return false; // 取零或重复了
backup[x] = true; // 标记
}
for (int i = 1; i <= 9; i ++ ) // 有没有出现的
if (!backup[i])
return false;
return true;
}
void dfs_c(int u, int a, int c) // 枚举c
{
if (u > 9) return;
if (check(a, c)) ans ++ ; // 判断
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) // 枚举a
{
if (a >= n) return;
if (a) dfs_c(u, a, 0); // 枚举c
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 << ans << endl;
return 0;
}