“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

解题思路： 按题目来看，我们大致需要完成一个素数筛和一个gcd(求最大公约数),然后就可以直接暴力搜A的数，在用一个邻接表把答案存起来可以了。到目前位置思路很简单，但是这样会发现超时了。这里给出一个优化的方法，根据题意，我们可以发现每个A最后一个数，必然是9。因为满足gcd(A，A + 1) > 2 的情况，只有A的最后一个数是9的情况，如果不明白的话，找几个例子带入一下，比如，A = 8, 则gcd(8,9) == 1而 A = 19 ，gcd(10,2) = 2.(gcd里面是m，n)。那我们枚举直接从百位数开始枚举就可以了(从十位数枚举还是会超时).

这里面线性筛不用也可以，因为这个题目的素数最大也不会过90，大家喜欢用什么素数筛都就用什么素数筛

#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int primes[N],cnt = 0;
bool st[N];
void get_priem(int n)                     //素数筛
{
    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)                      //位数相加
{
    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;
}

结语

本题是pat为数不多会卡时间复杂度的题目，优化的方法也很特殊，总得来说考察的知识点还是挺多的，最后顺便试试markdown编辑器。