1104 天长地久 – PAT乙级真题

“天长地久数”是指一个 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

分析：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题解离线版