1160 Forever – PAT甲级真题

“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

题目大意：“天长地久数”是指一个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。
分析：sum记录A的各位数字之和，sum2记录A+1的各位数字之和，I与II分别为数A与A+1。由打表观察可得，所有天长地久数最后两位为”99″，那么将末尾的两个’9’隐藏后可直接带入暴力循环判断。将所有可能答案存储后排序输出即可~

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
struct node {
    int n, num;
    friend bool operator < (node &a, node &b) {
        if (a.n != b.n) return a.n < b.n;
        return a.num < b.num;
    }
}T;
int N, K, m, temp, sum, sum2, I, II;
vector<node> A;
int is_prime(int x) {
    if (x <= 2) return 0;
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0) return 0; 
    }
    return 1;
}
int main() {
    cin >> N;
    for (int i = 1 ; i <= N; i++) {
        A.clear();
        cout << "Case " << i << '\n';
        cin >> K >> m;
        if (K * 9 < m) cout << "No Solution\n";
        else {
            temp = pow(10, K - 2);
            for (int i = temp / 10; i < temp; i++) {
                sum = 18, sum2 = 0, I = i, II = i + 1;
                while (I) {
                    sum += I % 10;
                    I /= 10;
                    if (sum > m) break;
                }
                while (II) {
                    sum2 += II % 10;
                    II /= 10;
                }
                if (sum == m && is_prime(__gcd(m, sum2))) {
                    T.n = sum2, T.num = i;
                    A.push_back(T);
                }
            }
            sort(A.begin(), A.end());
            if (A.empty()) cout << "No Solution\n";
            for (auto &it : A) {
                cout << it.n << ' ' << it.num << "99\n";
            }
        }
        
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <cmath>

#include <algorithm>

using namespace std;

struct node {

int n, num;

friend bool operator < (node &a, node &b) {

if (a.n != b.n) return a.n < b.n;

return a.num < b.num;

}

}T;

int N, K, m, temp, sum, sum2, I, II;

vector<node> A;

int is_prime(int x) {

if (x <= 2) return 0;

for (int i = 2; i <= sqrt(x); i++) {

if (x % i == 0) return 0;

}

return 1;

}

int main() {

cin >> N;

for (int i = 1 ; i <= N; i++) {

A.clear();

cout << "Case " << i << '\n';

cin >> K >> m;

if (K * 9 < m) cout << "No Solution\n";

else {

temp = pow(10, K - 2);

for (int i = temp / 10; i < temp; i++) {

sum = 18, sum2 = 0, I = i, II = i + 1;

while (I) {

sum += I % 10;

I /= 10;

if (sum > m) break;

}

while (II) {

sum2 += II % 10;

II /= 10;

}

if (sum == m && is_prime(__gcd(m, sum2))) {

T.n = sum2, T.num = i;

A.push_back(T);

}

sort(A.begin(), A.end());

if (A.empty()) cout << "No Solution\n";

for (auto &it : A) {

cout << it.n << ' ' << it.num << "99\n";

}

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版