第十五届蓝桥杯C++B组第二场真题-质数变革

思路

由于给出的数据大小以及题意可知，这道题考察的应该是线性筛和二分查找，本人由于太弱了，没想到我居然之前接触过欧拉筛，应该也叫做线性筛吧，时间紧迫来不及多思考，比赛中用的朴素做法，估计能拿个1分2分这样，以下是我补题后的写法

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+3;                       //开到第一个大于1000000的质数 
const int M = 2e5+10;
int n,q;
vector<int> cha[M];                        //查找值
int a[M];                                  //初始数组a
int pri[N],pri_num=0,lu[N],qp=0;           //质数，质数个数,记录因子数组 
bool ji[N],zhi[M];
inline void dabiao(){                      //欧拉筛
    for(int i=2;i<=N;i++){
        if(!ji[i]) lu[++qp]=i;
        for(int j=1;lu[j]*i<=N;j++){
            ji[lu[j]*i]=true;
            if(i%lu[j]==0) break;
        }
    }
    for(int i=2;i<=N;i++){
        if(!ji[i]) pri[++pri_num]=i;
    }
    return ;
}
inline int find_da(int x){                   //在质数表里寻找第一个大等于a[i]的数
    int l=1,r=pri_num;
    while(l<r){
        int mid=l+r>>1;
        if(pri[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r;
}
inline int find_xiao(int x){                 //在质数表里寻找第一个小等于a[i]的数
    int l=1,r=pri_num;
    while(l<r){
        int mid=l+r+1>>1;
        if(pri[mid]<=x) l=mid;
        else r=mid-1;
    }
    return l;
}
inline int he(int i){                      //找要替换成的数
    int sum=0;
    for(auto e:cha[i]){
        sum+=e;
    }
    return sum;
}
inline void tihuan(){                      //替换
    for(int i=1;i<=n;i++){
        if(cha[i].size()>0){
            if(!zhi[i]){                   //如果不是质数要把其按照第一次的变化变为质数，如果第一次是往大取，则先变小一位质数，反之则取大一位的质数
                int first=cha[i][0];
                if(first>0){
                    int pri_ai=find_xiao(a[i]);
                    a[i]=pri[pri_ai];
                }
                else{
                    int pri_ai=find_da(a[i]);
                    a[i]=pri[pri_ai];
                }
            }
            int sum=he(i);
            if(sum>0){
                int pri_ai=find_xiao(a[i]);
                if(sum+pri_ai<pri_num){
                    a[i]=pri[pri_ai+sum];
                }
                else a[i]=1;
            }
            else{
                int pri_ai=find_da(a[i]);
                if(sum+pri_ai>0){
                    a[i]=pri[pri_ai+sum];
                }
                else a[i]=0;
            }
        }
    }
    return ;
}
int main(){
    scanf("%d %d",&n,&q);
    dabiao();                   //先打一个质数表
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(pri[find_da(a[i])]==a[i]){     //记录每一个数是不是质数
            zhi[i]=true;
        }
    }
    while(q--){
        int op,k,x;
        scanf("%d %d %d",&op,&k,&x);
        for(int i=k;i<=n;i+=k){
            if(op==1){
                cha[i].push_back(x);        //记录每一次的搜索
            }
            else{
                cha[i].push_back(0-x);
            }
        }
    }
    tihuan();                   //替换   
    for(int i=1;i<=n;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    return 0;
}