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

· · 题解

题目传送门

枚举

在做这道题时，我第一眼枚举，因为本题时限十分宽松，每次枚举 a_{i} + b_{j} 的和 S，再判断 S 是否符合条件（S \leq n + m 且 S 为质数）。

就这样我得了 40 分，这是暴力的解法，相信大家都会暴力。

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
int n, m;
bool is_prime(int s){
    if (s <= 1) return 0;
    if (s == 2) return 1;
    if (s % 2 == 0) return 0;
    for (int i = 3; i * i <= s; i += 2) {
        if (s % i == 0) return 0;
    }
    return 1;
}

int main() {
    cin >> n >> m;

    vector<int> a(n),b(m);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }

    unordered_set<int> ans;

    for (int ai : a) {
        for (int bj : b) {
            int S = ai + bj;
            if (S <= m+n && is_prime(S)) {
                ans.insert(S);
            }
        }
    }

    cout << ans.size() << endl;

    return 0;
}

改进

但我 TLE 了，经过我仔细思考，每一次得到的 S 都会判断一遍是不是素数；但 S 可能会有重复，以至于我们重复判断一个数是不是素数，这会增加额外的时间开支，我们可以在程序开始前把所有可能的 S 都判断一遍是不是素数（也就是预处理），这样可以减少时间开支；因为 S \leq n + m 所以 S 最大为 n+m。

埃氏筛法

我们通过埃氏筛法预处理素数，它是一种用于快速筛选所有小于给定数 N 的质数的经典算法。埃氏筛法的核心思想是通过逐步排除合数（非质数）来找到所有质数，它的理论时间复杂度为 O(N \log \log N)。

示例

vector<bool> sieve() { // 埃拉托斯特尼筛法（也称埃氏筛法）。
    vector<bool> is_prime(max_S + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= max_S; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= max_S; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return is_prime;
}

就这样我 AC 了

以下是 AC 代码，完结撒花。 (〃'▽'〃)

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
int n,m;
int max_S;
vector<bool> sieve() {
    vector<bool> is_prime(max_S + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= max_S; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= max_S; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return is_prime;
}

int main() {
    cin >> n >> m;
    max_S = n + m;

    vector<int> a(n),b(m); // 提前规划内存大小，便于直接访问。
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }

    vector<bool> is_prime = sieve();
    /* unordered_set 与 set 比较，
       它在内部不会自动排序，降低时间复杂度。 */
    unordered_set<int>  ans;

    for (int ai : a) {
        for (int bj : b) {
            int S = ai + bj;
            if (S <= max_S && is_prime[S]) {
                ans.insert(S);
            }
        }
    }

    cout << ans.size() << endl;

    return 0;
}

有错误请在评论区指出，谢谢。