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

· · 题解

前置芝士 线性筛 本题精髓

//线性筛(前置芝士P3383) 
void prime() {
    for (int i = 2; i <= n + m; i++) {
        if (!isp[i]) {
            p[++cnt] = i;
        }
        for (int j = 1; j <= cnt && i * p[j] <= n + m; j++) {
            isp[i * p[j]] = 1;
            if (i % p[j] == 0) {
                break;
            }
        }
    }
}

题意

给你两个数组 a 和 b 问你利用这两个数组中的数字，可以组合出多少符合要求的不重复的组合，要求为将 a 数组中的任意一个数与 b 数组中的任意一个数相加，得到 s 这个数，我们的 s 需要是质数，且 s 小于等于 n 与 m 的和。

思路

我们可以先筛小于 n 与 m 的和的质数，运用 isp 数组来看某一个数是否是质数，在输入之后，我们可以使用两重循环，因为题目给了三秒的时间，所以暴力就可以，我们再看我们的 a_i 与 b_j 的和 t 是否符合要求，而且没有重复的，我们就可以将答案加一，并且将这个数的 vis 标为访问过，最后输出答案。 本题主要考察的是会不会筛素数与会不会去重，没有别的，只是基本语法，并无难点。

代码

#include <bits/stdc++.h>
using namespace std;
int n, m; //上半句与下半句的数量
int a[50005];//上半句 
int b[50005];//下半句 
int p[100001];//存质数 
int cnt = 0;
int isp[100001];//质数判断 
int vis[100001];//组合判重 
int sum=0;//总数 
void prime() {
    for (int i = 2; i <= n + m; i++) { //只找n+m以下的质数(线性筛)(埃式筛也可以)
        if (!isp[i]) {
            p[++cnt] = i;
        }
        for (int j = 1; j <= cnt && i * p[j] <= n + m; j++) {//线性筛(前置芝士P3383) 
            isp[i * p[j]] = 1;
            if (i % p[j] == 0) {
                break;
            }
        }
    }
}
int main() {
    cin >> n >> m;
    prime();//筛素数 
    for (int i = 1; i <= n; i++) {//输入前半句 
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {//输入下半句 
        cin >> b[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){//三秒钟，暴力即可 
            int t=a[i]+b[j];//总和 
            if(isp[t]==0&&t<=n+m&&vis[t]==0){//判断是否符合条件 
                sum++;//增加 
                vis[t]=1; //标记 
            } 
        }
    }
    cout << sum;
    return 0;//好习惯 
}