[PAT-A] 1160 Forever

Java

import java.io.*;
import java.util.*;

public class Main {
    static class Solution implements Comparable<Solution> {
        int n, A;

        Solution(int n, int A) {
            this.n = n;
            this.A = A;
        }

        @Override
        public int compareTo(Solution other) {
            if (this.n != other.n) {
                return Integer.compare(this.n, other.n);
            }
            return Integer.compare(this.A, other.A);
        }
    }

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

    static boolean isPrime(int n) {
        if (n <= 1) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    static int digitSum(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int Q = Integer.parseInt(br.readLine());

        for (int caseNum = 1; caseNum <= Q; caseNum++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            List<Solution> results = new ArrayList<>();
            System.out.println("Case " + caseNum);

            int start = (int) Math.pow(10, k - 1);
            boolean found = false;

            for (int A = start + 9; A < start * 10; A += 10) {
                int sumA = digitSum(A);
                if (sumA != m) continue;

                int n = digitSum(A + 1);

                int d = gcd(m, n);
                if (isPrime(d) && d > 2) {
                    results.add(new Solution(n, A));
                    found = true;
                }
            }

            if (!found) {
                System.out.println("No Solution");
            } else {
                Collections.sort(results);
                for (Solution sol : results) {
                    System.out.println(sol.n + " " + sol.A);
                }
            }
        }
    }
}

C++

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

int Q, k, m;

struct Solution {
    int n, A;

    bool operator<(const Solution &t) const {
        if (n != t.n) return n < t.n;
        else return A < t.A;
    }
};

vector<Solution> res;

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

int is_prime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= n / i; ++i)
        if (n % i == 0) return false;
    return true;
}

int main() {
    scanf("%d", &Q);
    for (int num = 1; num <= Q; ++num) {
        scanf("%d%d", &k, &m);
        res.clear();
        printf("Case %d\n", num);

        int start = pow(10, k - 1);
        bool success = false;
        for (int A = start + 9; A < start * 10; A += 10) {
            int sum = 0, tmpA = A;
            while (tmpA) {
                sum += tmpA % 10;
                tmpA /= 10;
            }

            if (sum != m) continue;

            int n = 0, A1 = A + 1;
            while (A1) {
                n += A1 % 10;
                A1 /= 10;
            }

            int d = gcd(m, n);
            if (is_prime(d) && d > 2) {
                res.push_back({n, A});
                success = true;
            }
        }

        if (!success) printf("No Solution\n");
        else {
            sort(res.begin(), res.end());
            for (auto it: res)
                printf("%d %d\n", it.n, it.A);
        }

    }

    return 0;
}