给出一个数的位数，及各位数之和，判断是否是forerver 数。 分析：这里从高位开始，如果左边各位数之和小于等于题目中所给的数字,且当右边所有数均为9时，各位数之和大于所给数字。如给定的位数为5，和为45，则当数字是12xxx,当低位均为9，即12999，各位数之和30依然小于45，说明高位的12应该更大。利用这样的条件进行DFS剪枝。
#include<cstdio> #include<string> #include<cmath> #include<vector> using namespace std; int N, k, m; struct node{ int n, val; friend bool operator < (node a, node b) { if(a.n != b.n) return a.n < b.n; else return a.val < b.val; } }; int gcd(int a, int b) { if(b == 0) return a; else return gcd(b , a % b); } bool isPrime(int x) { if(x <= 2) return false; for(int i = 3; i*i <= x; i++) if(x % i == 0) return false; return true; } int getTotal(int x) { int sum = 0; while(x != 0) { int r = x % 10; sum += r; x /= 10; } return sum; } vector<node> res; void DFS(int num, int sum, int rest_k) { if(rest_k == 0) { if(sum == m) { int n = getTotal(num+1); int r = gcd(m, n); if(isPrime(r)) res.push_back({n, num}); return; } } if(rest_k > 0) { for(int i = 0; i <= 9; i++) { if(sum + i + (rest_k-1)*9 >= m && sum + i <= m) DFS(num*10+i, sum+i, rest_k-1);//低位的数可为0 } } } int main() { scanf("%d", &N); for(int i = 1; i <= N; i++) { scanf("%d%d", &k, &m); printf("Case %d\n", i); res.clear(); for(int i = 1; i <= 9; i++) DFS(i, i, k-1);\\最高位数字不能为0 if(res.size() == 0) printf("No solution\n"); else { for(int i = 0; i < res.size(); i++) printf("%d %d\n", res[i].n, res[i].val); } } }