Pat class a 1160 forever (class B 1104 forever)

“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

Their thinking ： By topic , We roughly need to complete a prime sieve and a gcd( Find the greatest common divisor ), Then you can search directly and violently A Number of numbers , Save the answers with an adjacency table . So far, the idea is very simple , But in this way, you will find that it has timed out . Here is an optimization method , According to the meaning , We can find each one A Last number , It must be 9. Because of satisfaction gcd(A,A + 1) > 2 The situation of , Only A The last number is 9 The situation of , If you don't understand , Find a few examples to bring in , such as ,A = 8, be gcd(8,9) == 1 and A = 19 ,gcd(10,2) = 2.(gcd Inside is m,n). Then we can enumerate directly from the hundreds ( Enumerating from ten digits will still timeout ).

The linear screen can be used without , Because the prime number of this topic is not too large 90, You can use whatever prime sieve you like

#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int primes[N],cnt = 0;
bool st[N];
void get_priem(int n)                     // Prime sieve 
{
    
    for (int i = 2; i <= n; i ++ )
    {
    
        if(!st[i]) primes[cnt ++ ] = i;
        for (int j = 0 ;primes[j] * i <= n; j ++ )
        {
    
            st[primes[j] * i] = 1;
            if(i % primes[j] == 0) break;
        }
    }
}
int gcd(int a,int b)                // gcd
{
    
    return b ? gcd(b,a % b) : a;
}
int cal(int n)                      // Add the digits 
{
    
    int num = 0;
    while(n > 0)
    {
    
        num += (n % 10);
        n /= 10;
    }
    return num;
}
int main()
{
    
    int k,m,t;
    scanf("%d",&t);
    get_priem(N);
    for (int Case = 1; Case <= t; Case ++ )
    {
    
        printf("Case %d\n",Case);
        scanf("%d %d",&k,&m);
        bool flag = 0;
        vector<int> v[100];
        for (int i = pow(10,k - 1) + 99; i <= pow(10,k) - 1; i += 100 )          
        {
    
            int num = cal(i);
            if(num == m)
            {
    
                int n = cal(i + 1);
                int d = gcd(n,m);
                if(!st[d] && d > 2)
                {
    
                    v[n].push_back(i);
                }
            }
        }
        for (int i = 0; i < 90 ; i ++ )
        {
    
            for (int j = 0; j < v[i].size();j ++ )
            {
    
                printf("%d %d\n",i,v[i][j]);
                flag = 1;
            }
        }
        if(!flag) printf("No Solution\n");
    }
    return 0;
}

Conclusion

The subject is pat One of the few topics that will card time complexity , The optimization method is also very special , In general, the knowledge points investigated are quite many , Finally, try it by the way markdown Editor .