题目：

“天长地久数”是指一个 K 位正整数 A，其满足条件为：A 的各位数字之和为 m，A+1 的各位数字之和为 n，且 m 与 n 的最大公约数是一个大于 2 的素数。本题就请你找出这些天长地久数。

输入格式：

输入在第一行给出正整数 N（≤5），随后 N 行，每行给出一对 K（3<K<10）和 m（1<m<90），其含义如题面所述。

输出格式：

对每一对输入的 K 和 m，首先在一行中输出 Case X，其中 X 是输出的编号（从 1 开始）；然后一行输出对应的 n 和 A，数字间以空格分隔。如果解不唯一，则每组解占一行，按 n 的递增序输出；若仍不唯一，则按 A 的递增序输出。若解不存在，则在一行中输出 No Solution。

输入样例：

2
6 45
7 80

输出样例：

Case 1
10 189999
10 279999
10 369999
10 459999
10 549999
10 639999
10 729999
10 819999
10 909999
Case 2
No Solution

分析：

我的做法如下：

根据位数k，生成下限和上限，比如k=5，区间则为[10000，99999]；然后在区间内暴力搜索A、A+1，将整数转换为string求各位数字之和；A和A+1各位数字之和的公约数，既要大于2，又要是个素数；但数据比较多，会超时。

后来看到别人说，根据打表可知所有数末尾都是"99"（没看懂为啥），因此搜索起点变为下限+99，间隔为100；暴力搜索A，通过。

代码：

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;

long long gcd(long long t1, long long t2)   //求最大公约数
{
    return t2 == 0 ? t1 : gcd(t2, t1 % t2);
}

int strsum(long long a)
{
    string s = to_string(a);
    int sum = 0;
    for(int i = 0; i < s.length(); i++)
        sum += (s[i] - '0');
    return sum;
}

bool isprime(long long n)
{
    for(long long i = 2; i <= sqrt(n); i++)
        if(n % i == 0)
            return false;
    return true;
}

struct RESULT
{
    int n;
    long long A;
};

bool cmp(RESULT r1, RESULT r2)
{
    if(r1.n != r2.n) return r1.n < r2.n;
    else return r1.A < r2.A;
}
RESULT rs[10000000];
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int k, m;
        cin >> k >> m;
        string _min = "1" + string(k-1, '0');
        string _max = string(k, '9');
        long long min = stoll(_min);
        long long max = stoll(_max);
        cout << "Case " << i + 1 << endl;
        long long cnt = 0;
        for(long long j = min + 99; j <= max; j+=100)
        {
            int sj = strsum(j);
            int sj1 = strsum(j+1);
            if(sj == m)
            {
                long long common = gcd(sj, sj1);
                if(common > 2 && isprime(common))
                {
                    rs[cnt].n = sj1; rs[cnt].A = j;
                    cnt++;
                }
            }
        }
        if(cnt==0) cout << "No Solution" << endl;
        else
        {
            sort(rs, rs+cnt, cmp);
            for(int j = 0;j < cnt; j++)
                cout << rs[j].n << " " << rs[j].A << endl;
        }
    }
    return 0;
}