19年秋季第一题 PAT甲级 1161 Forever (20 分) 有点儿意思

水深无声 2023-07-04 08:40 11阅读 0赞

如果喜欢我的文章请点赞让我知道噢

# 题目 #

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

# 事先准备 #

这道题会用到几个小的工具函数，一定要准备好：

//求最大公约数
    int gcd(int a,int b){
        return b==0?a:gcd(b,a%b);
    }
    
    //检验不小于3的素数
    bool isPrime(int n){
        if(n<3)return false;
        int x=(int)sqrt(n);
        for(int i=2;i<=x;i++){
            if(n%i==0)return false;
        }
        return true;
    }
    
    //求整数的每一位数之和
    int sum(int n){
        return n==0?0:sum(n/10)+n%10;
    }

# 陷阱 #

如果不按照尾数为99的数枚举，会超时。

那你是怎么就这么肯定的呢？

首先题目是Forever数，“长长久久”暗示了该有两个九。其次呢，加一不进位的话，这两个数的各位之和相差的是1，无论如何也不会有不小于三的最小公约数了吧。提出了这个假设之后可以自己写一段程序验证一下。

# 代码  #

//得分:20，满分
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <set>
    #include <map>
    #include <cmath>
    using namespace std;
    int k, n,m,a,b,c,d,num;
    bool f=false;
    struct node{
        int n,a;
    };
    int gcd(int a,int b){
        return b==0?a:gcd(b,a%b);
    }
    bool isPrime(int n){
        if(n<=2)return false;
        int sq=(int)sqrt(n);
        for(int j=2;j<=sq;j++){
            if(n%j==0)return false;
        }
        return true;
    }
    int sum(int n){
        return n==0? 0: n%10 + sum(n/10);
    }
    bool cmp(node &a,node &b){
        if(a.n!=b.n)return a.n<b.n;
        return a.a<b.a;
    }
    int main() {
        scanf("%d", &n);
        for(int i=0;i<n;i++){
            scanf("%d %d",&k,&m);
            printf("Case %d\n",i+1);
            a=(int)pow(10,k-3);//-3
            b=a*10;
            vector<node> v;
            for(int x=a;x<b;x++){
                c=x*100+99;
                d=sum(c+1);
                if(sum(c)==m && isPrime(gcd(d,m))){
                    v.push_back({d,c});
                }
    //        这段注释掉的代码可以验证尾数为99才行           
    //        a=(int)pow(10,k-1);
    //        b=a*10;
    //        for(int x=a;x<b;x++){
    //            d=sum(x+1);
    //            if(isPrime(gcd(d,sum(x))) && x%100!=99)
    //                printf("%d %d %d %d\n",d,x,sum(x),gcd(d,sum(x)));
    //        }
            
            if(v.size()==0)printf("No Solution\n");
            else{
                sort(v.begin(),v.end(),cmp);
                for(auto it:v){
                    printf("%d %d\n",it.n,it.a);
                }
            }
        }
        
        return 0;
    }

如果喜欢我的文章请点赞让我知道噢