自动搬运

查看原文

来自洛谷，原作者为

	weizilong 绿标迟早有一天会变成金标的

搬运于2025-08-24 23:13:14，当前版本为作者最后更新于2025-04-16 13:28:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

枚举

在做这道题时，我第一眼枚举，因为本题时限十分宽松，每次枚举 $$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;
}

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