乐趣区

关于算法-数据结构:PAT甲级2019年秋季考试-71-Forever

jiezi

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:

2
6 45
7 80

Sample Output:

Case 1
10 189999
10 279999
10 369999
10 459999
10 549999
10 639999
10 729999
10 819999
10 909999
Case 2
No 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;
}
退出移动版