本题来自于第四届蓝桥杯省赛C++B/C组，对于刚开始学习算法的人来讲可能相对较难，题目要求将一个分数分解成三个部分，一个整数一个分子一个分母，这里分别用a b c 来分别表示。同时要求1~9的所有数字都必须出现，且不能出现0。这里至少我们可以将数字的使用个数固定，不妨通过枚举的方式，对a c进行枚举(b的数字较c大所以枚举c的效率更高)。之后用剩下的位数将b反推出来，最后用数学方法判断当前的方案是否可行，若可行便可以记录在结果之中，全部枚举一遍之后就可以得出最后的答案。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N = 10; bool sta[N], backup[N]; int n, ans; bool check(int a, int c) //判断方案的可行性 { long long b = n * (long long)c - a * c; if (!a || !c || !b) return false; memcpy(backup, sta, sizeof(sta)); while (b) { int z = b % 10; if (!z || backup[z]) return false; backup[z] = true; b /= 10; } for (int j = 1; j <= 9; j++) { if (!backup[j]) { 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 (!sta[i]) { sta[i] = true; dfs_c(u + 1, a, c * 10 + i); sta[i] = false; } } } void dfs_a(int u, int a) //枚举a { if (a >= n) return; if (a) dfs_c(u, a, 0); for (int i = 1; i <= 9; i++) { if (!sta[i]) { sta[i] = true; dfs_a(u + 1, a * 10 + i); sta[i] = false; } } } int main() { scanf("%d", &n); dfs_a(0, 0); cout << ans << endl; return 0; }
