班班最大了

##思路
由于给出的数据大小以及题意可知，这道题考察的应该是线性筛和二分查找，本人由于太弱了，没想到我居然之前接触过欧拉筛，应该也叫做线性筛吧，时间紧迫来不及多思考，比赛中用的朴素做法，估计能拿个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;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

班班最大了

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （C++代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

回文数字（C++代码）

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

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

评论区

精彩推荐

蓝桥杯历届试题-九宫重排（C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言考试练习题_保留字母（C语言代码）

最小公倍数（C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

核桃的数量（C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

班班最大了

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （C++代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

回文数字 （C++代码）

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

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

评论区

精彩推荐

蓝桥杯历届试题-九宫重排 （C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言考试练习题_保留字母 （C语言代码）

最小公倍数 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

核桃的数量 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

回文数字（C++代码）

　　评论区

蓝桥杯历届试题-九宫重排（C++代码）

C语言考试练习题_保留字母（C语言代码）

最小公倍数（C语言代码）

核桃的数量（C语言代码）