刚刚以为哪里有问题删帖了,重发一遍。
void init(){
memset(miu,-1,sizeof miu);
miu[0]=0,miu[1]=1;
for(int i=2;i<=N-10;i++){
if(miu[i]==-1)p[++pc]=i;
for(int j=1,x;j<=pc&&(x=i*p[j])<=N-10;j++){
if(i%p[j]==0){miu[x]=0;break;}
miu[x]=-miu[i];
}
}
for(int i=1;i<=N-10;i++)miu[i]+=miu[i-1];
}
错误原因是显然的,我也不知道为啥我刚开始会想到这么写。
跑完之后输出 p,发现例如 30,42,2022 的数都被识别成了质数。
这么写错能过板子,所以我问一下这个的复杂度。
如果想让这种错误写法 TLE 的话又要多大的数据呢。
主要是它内层循环枚举所有素数的时候会错误的枚举到合数,我不知道这个对复杂度有没有影响/kel