题解：P12157 [蓝桥杯 2025 省 Java B] 魔法科考试

prh_rpjiajia · 2025-04-19 08:55:13 · 题解

解题步骤

1. 质数判断

直接对每个 S 进行质数判断会超时，我们可以想到——用筛法，先用埃筛筛出质数。由于 S 的最大可能值是 n + m，筛法的范围设成 n + m 就行了。

2. 暴力遍历

暴力枚举，对于每一个 a_i 和 b_j，计算 S = a_i + b_j，并检查。

3. 统计结果

使用一个标记数组记录已经出现过的 S，确保每个 S 只被统计一次。

代码实现

既然是 Java 组，当然就要有 Java 代码啦。码风有一点点丑。

import java.util.Scanner;

public class Main {
    static final int MAX = 40010; 
    static boolean[] P = new boolean[MAX]; 
    static boolean[] V = new boolean[MAX];

    static void sieve(int limit) {
        for (int i = 2; i <= limit; i++) {
            P[i] = true;
        }
        P[0] = P[1] = false;
        for (int i = 2; i * i <= limit; i++) {
            if (P[i]) {
                for (int j = i * i; j <= limit; j += i) {
                    P[j] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[m];

        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        for (int i = 0; i < m; i++) b[i] = sc.nextInt();

        int limit = n + m;
        sieve(limit);

        int cnt = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int s = a[i] + b[j];
                if (s <= limit && P[s] && !V[s]) {
                    V[s] = true;
                    cnt++;
                }
            }
        }

        System.out.println(cnt);
    }
}

检查一下复杂度

• 埃筛：时间复杂度 O(n \log \log n)，其中 n 是筛法的上限 n + m。
• 暴力：时间复杂度 O(n \times m)，其中 n 和 m 最大为 20000，可以接受。
• 空间复杂度：O(n + m)，不会爆空间。

这题就被完美解决了，撒花！！！