7-1 Forever (20分)

"Forever number" is a positive integer A with K digits, satisfying the following constrains:

  • the sum of all the digits of A is m;
  • the sum of all the digits of A+1 is n; and
  • the greatest common divisor of m and n is a prime number which is greater than 2.

Now you are supposed to find these forever numbers.

Input Specification:

Each input file contains one test case. For each test case, the first line contains a positive integer N (≤5). Then N lines follow, each gives a pair of K (3<K<10) and m (1<m<90), of which the meanings are given in the problem description.

Output Specification:

For each pair of K and m, first print in a line Case X, where X is the case index (starts from 1). Then print n and A in the following line. The numbers must be separated by a space. If the solution is not unique, output in the ascending order of n. If still not unique, output in the ascending order of A. If there is no solution, output No Solution.

Sample Input:

26 457 80

Sample Output:

Case 110 18999910 27999910 36999910 45999910 54999910 63999910 72999910 81999910 909999Case 2No Solution

题目限度：

题目粗心：

现给定一个数字A的总位数K和所有位数之和m,要求你寻找这样的一个数字n,n为A+1的所有数位之和，m和n的最大公约数G，并G大于2且为素数，输入所有的n和A，否则输入No Solution。

算法思路：

第一反馈此题和全排列的问题即为类似，就是增加了约束条件。那么其本质就是使用暴力搜寻，很容易就想到应用DFS进行求解。然而间接进行DFS最初一个点会超时，所以得弄清楚剪枝条件，咱们假如当初搜寻到第depth位，以后的总数位之和为m,数字为num,那么前面还没有搜寻的数位有K-depth位。那么剪枝的条件就是，如果以后的总数位之和m+前面未搜寻的最大总数位之和9*(K-depth)小于K，那么就阐明无论怎样取值，都不可能存在一个数的总数位m合乎题目要求。这样DFS的超时问题就解决了，当初只须要求解任意2数的最大公约数和任意一个数字的位数之和,就能够编写DFS函数了。

求解最大公约数的办法，这里给出2种：
// 实用于a,b较小的状况int gcd(int a,int b){    if(b==0) return a;    return gcd(b,a%b);}// 实用于a,b较大的状况(编程之美2.7章节)int gcd(int a,int b){    if(a<b) return gcd(b,a);    if(b==0){        return a;    } else {        if(a%2==0){            if(b%2==0){                return 2*gcd(a/2,b/2);            } else {                return gcd(a/2,b);            }        } else{            if(b%2==0){                return gcd(a,b/2);            } else {                return gcd(b,a-b);            }        }    }}
对于任意一个数字num,其总位数之和：
int getDigitSum(int num){    int m = 0;    while (num!=0){        m += num%10;        num /= 10;    }    return m;}
DFS函数：
/* * depth:以后深度，代表抉择第几位，初始为0 * m:以后曾经抉择的位数之和，比方抉择了3次，别离是1，4，5，那么m=1+4+5=10 * num:以后曾经抉择的位数所代表的数字，比方抉择了3次，别离是1，4，5，那么num=145 * */void DFS(int depth,int m,int num){    if(depth==K&&m==M){        int n = getDigitSum(num+1);// 失去n        int G = gcd(m,n);        if(G>2&&isPrime(G)){            // 保留后果集            result.emplace_back(num,n);        }        return;    }    // 残余最大值之和都小于所须要的，不可能有解    if(m+9*(K-depth)<M||depth>K) return;    for(int i=0;i<=9;++i){        DFS(depth+1,m+i,num*10+i);    }}

到这里DFS并没有完结，因为还有能够优化的点(下面的代码曾经能够通过测试了)，因为第一位肯定是1，不可能是0，最初两位肯定是99。第一位是1比拟好想的到，最初两位为什么是99呢？

首先对于任意2个相邻数字的最大公约数为1，比方6和7，要想m和n的最大公约数大于2，首先就是要求m和n不能是相邻的两个数字，那么要求m和n不相邻，就得保障A的最初一个数字得是9，不然A+1没有进位,n=m+1。然而如果只有最初一位为9仍然还是不行，因为如果只有一个9，那么A+1的所有数位之和n=m-9+1(最初的9进位了),那么n与m的最大公约数等价于8和m的最大公约数(辗转相除法,不懂得看编程之美2.7章节)，然而8的约数只有1，2，4，8，均不是大于2的素数，所以最初一位还得是9，因为不是9的化，n仍然等于m-8。最初2位为9当前,n=m-9-9+1(2个9都进位了)，这样n和m的公约数就转化为m和17的公约数了，如果m恰好整除17，就失去了一个大于2的素数，所以最初2位肯定是9。

依据以上剖析，优化后的DFS如下：
/* * depth:以后深度，代表抉择第几位，初始为0 * m:以后曾经抉择的位数之和，比方抉择了3次，别离是1，4，5，那么m=1+4+5=10 * num:以后曾经抉择的位数所代表的数字，比方抉择了3次，别离是1，4，5，那么num=145 * */void DFS(int depth,int m,int num){    if(depth==K&&m==M){        int n = getDigitSum(num+1);// 失去n        int G = gcd(m,n);        if(G>2&&isPrime(G)){            result.emplace_back(num,n);        }        return;    }    // 残余最大值之和都小于所须要的，不可能有解    if(m+9*(K-depth)<M||depth>K) return;    // 第一位肯定为1，最初2位肯定为9    int i = depth==0 ? 1: depth==K-1||depth==K-2? 9 : 0;    for(;i<=9;++i){        DFS(depth+1,m+i,num*10+i);    }}

最初应用result保留所有的后果集，而后排序输入即可。

留神点：

  • 1、排序是必须的，不然测试点2无奈通过(卡了我1小时，本来认为曾经有序)

提交后果：

AC代码：

#include<cstdio>#include<vector>#include<cmath>#include <algorithm>using namespace std;struct Node{    int A;    int n;    Node(int _A,int _n){        A = _A;        n = _n;    }};int K,M;// 总位数，总位数之和vector<Node > result;bool cmp(const Node &a,const Node &b){    return a.n!=b.n?a.n<b.n:a.A<b.A;}int gcd(int a,int b){    if(b==0) return a;    return gcd(b,a%b);}bool isPrime(int n){    if(n<=1) return false;    int sqrtn = (int)sqrt(n*1.0);    for(int i=2;i<=sqrtn;++i){        if(n%i==0) return false;    }    return true;}int getDigitSum(int num){    int m = 0;    while (num!=0){        m += num%10;        num /= 10;    }    return m;}/* * depth:以后深度，代表抉择第几位，初始为0 * m:以后曾经抉择的位数之和，比方抉择了3次，别离是1，4，5，那么m=1+4+5=10 * num:以后曾经抉择的位数所代表的数字，比方抉择了3次，别离是1，4，5，那么num=145 * */void DFS(int depth,int m,int num){    if(depth==K&&m==M){        int n = getDigitSum(num+1);// 失去n        int G = gcd(m,n);        if(G>2&&isPrime(G)){            result.emplace_back(num,n);        }        return;    }    // 残余最大值之和都小于所须要的，不可能有解    if(m+9*(K-depth)<M||depth>K) return;    // 第一位肯定为1，最初2位肯定为9    int i = depth==0 ? 1: depth==K-1||depth==K-2? 9 : 0;    for(;i<=9;++i){        DFS(depth+1,m+i,num*10+i);    }}int main(){    int N;    scanf("%d",&N);    for(int i=0;i<N;++i){        scanf("%d %d",&K,&M);        printf("Case %d\n",i+1);        result.clear();        DFS(0,0,0);        sort(result.begin(), result.end(),cmp);        for (auto &item : result) {            printf("%d %d\n",item.n,item.A);        }        if (result.empty()) {            printf("No Solution\n");        }    }    return 0;}