2019 PAT甲级秋季考试7-1 Forever (20 分)

深碍√TFBOYSˉ_ 2024-04-18 16:03 32阅读 0赞

"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

暴力王打表发现最后两位一定是99~

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define INF 0x3f3f3f3f
    int gcd(int a,int b)
    {
    	return a%b==0?b:gcd(b,a%b);
    }
    bool prime(int x)
    {
    	if(x<=2) return false;
    	for(int i=2;i<=sqrt(x);i++)
    	{
    		if(x%i==0)
    		return false;
    	}
    	return true;
    }
    int sumd(int x)
    {
    	int sum=0;
    	while(x)
    	{
    		sum+=x%10;
    		x=x/10;
    	}
    	return sum;
    }
    struct sb
    {
    	int op,val;
    }p[1000005];
    bool cmp(sb u,sb w)
    {
    	if(u.op!=w.op)return u.op<w.op;
    	else return u.val<w.val;
    }
    int main()
    {
    	int t,n,m,k,i,j,o=1;
    	scanf("%d",&t);
    	while(t--)
    	{	
    		int flag=0,uio=0;
    		scanf("%d%d",&k,&m);
    		printf("Case %d\n",o++);
    		if(k==4)
    		{
    			for(i=10;i<=99;i++)
    			{
    				if(sumd(i)+18==m)
    				{
    					int op=sumd(i+1);
    					if(prime(gcd(m,op)))
    					{
    						p[uio].op=op;
    						p[uio].val=i*100+99;
    						uio++;
    						//printf("%d %d\n",op,i*100+99);
    						flag++;
    					}
    				}
    			}
    		}
    		else if(k==5)
    		{
    			for(i=100;i<=999;i++)
    			{
    				if(sumd(i)+18==m)
    				{
    					int op=sumd(i+1);
    					if(prime(gcd(m,op)))
    					{
    						p[uio].op=op;
    						p[uio].val=i*100+99;
    						uio++;
    						//printf("%d %d\n",op,i*100+99);
    						flag++;
    					}
    				}
    			}
    		}
    		else if(k==6)
    		{
    			for(i=1000;i<=9999;i++)
    			{
    				if(sumd(i)+18==m)
    				{
    					int op=sumd(i+1);
    					if(prime(gcd(m,op)))
    					{
    						p[uio].op=op;
    						p[uio].val=i*100+99;
    						uio++;
    						//printf("%d %d\n",op,i*100+99);
    						flag++;
    					}
    				}
    			}
    		}
    		else if(k==7)
    		{
    			for(i=10000;i<=99999;i++)
    			{
    				if(sumd(i)+18==m)
    				{
    					int op=sumd(i+1);
    					if(prime(gcd(m,op)))
    					{
    						p[uio].op=op;
    						p[uio].val=i*100+99;
    						uio++;
    						//printf("%d %d\n",op,i*100+99);
    						flag++;
    					}
    				}
    			}
    		}
    		else if(k==8)
    		{
    			for(i=100000;i<=999999;i++)
    			{
    				if(sumd(i)+18==m)
    				{
    					int op=sumd(i+1);
    					if(prime(gcd(m,op)))
    					{
    						p[uio].op=op;
    						p[uio].val=i*100+99;
    						uio++;
    						//printf("%d %d\n",op,i*100+99);
    						flag++;
    					}
    				}
    			}
    		}
    		else if(k==9)
    		{
    			for(i=1000000;i<=9999999;i++)
    			{
    				if(sumd(i)+18==m)
    				{
    					int op=sumd(i+1);
    					if(prime(gcd(m,op)))
    					{
    						p[uio].op=op;
    						p[uio].val=i*100+99;
    						uio++;
    						//printf("%d %d\n",op,i*100+99);
    						flag++;
    					}
    				}
    			}
    		}
    		if(flag==0)
    		printf("No Solution\n");
    		else
    		{
    			sort(p,p+uio,cmp);
    			for(i=0;i<uio;i++)
    			printf("%d %d\n",p[i].op,p[i].val);
    		}
    	}
    }