筛法求莫比乌斯函数

什么是莫比乌斯函数

思路

模版

const int N=1000010;
int m[N],n[N],cnt=0;
int mu[N];//记录i的莫比乌斯函数值
void get_mu(int x)//筛法求莫比乌斯函数
{ mu[1]=1;for(int i=2;i<=x;i++){if(!m[i]){n[++cnt]=i;mu[i]=-1;}for(int j=1;i*n[j]<=x;j++){int p=i*n[j];m[p]=1;if(i%n[j]==0){mu[p]=0;break;}elsemu[p]=-mu[i];}} 
}