A1160 Forever (20 分)

A1160 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

题目大意：

“Forever number” 是一个K位数字的正整数，满足以下约束条件：

• A中数字之和为m
• A + 1 中数字之和为n
• m 和 n 的最大公约数是大于2的素数

现在让我们找出这些“Forever number”。

input：N，K，m

output：Case X 输出的结果按n递增排序，如果n相同则按A递增排序，如果没有“Forever number”，则输出No Solution

思路

1. 发现规律：满足“Forever number”的数的末尾两位是99
2. 根据规律的条件进行暴搜

3. 注意点：

   • the greatest common divisor 的翻译：最大公约数，简写为（gcd）
   • m 和 n 的公约数要大于2，不能等于2（虽然2是素数）（PS：我就在这里找了好久???）

AC代码

#include<bits/stdc++.h>
using namespace std;

int digitalSum(int x) {
    return x == 0 ? 0 : digitalSum(x/10) + x % 10;
}

bool isPrime(int x) {
    if (x <= 2) return false;
    int sqt = sqrt(x * 1.0);
    for (int i = 2; i <= sqt; ++i) {
        if (x % i == 0) return false;
    }
    return true;
}

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

bool cmp (const pair<int, int> &p1, const pair<int, int> &p2) {
    return p1.first != p2.first ? p1.first < p2.first : p1.second < p2.second;
}

int main() {
    int n;
    int k, m;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        printf("Case %d\n", i + 1);
        scanf("%d%d", &k, &m);
        vector<pair<int, int> > res;
        int bg = int(pow(10, k - 3));
        for (int x = bg; x < bg * 10; ++x) {
            int num = x * 100 + 99;
            int sum = digitalSum(num + 1);
            if (digitalSum(num) == m && isPrime(gcd(sum, m))) {
                res.emplace_back(sum, num);
            }
        }
        if (res.empty()) printf("No Solution\n");
        else {
            sort(res.begin(), res.end(), cmp);
            for (auto &p : res) printf("%d %d\n", p.first, p.second);
        }
    }
    return 0;
}