『算法-ACM 竞赛-数学-数论』莫比乌斯线性筛模板

ACM 常用模板合集

int  prime[MAXN],prime_tot;
bool isprime[MAXN];
int mu[MAXN];
void pre_calc(int  limt)
{
    mu[1]=1;
    for(int i=2;i<=limt;i++)
    {
        if(!isprime[i]){
            prime[prime_tot]=i;
            mu[i]=-1;
        }
        for (int j=1;j<prime_tot;j++)
        {
            if(i*prime[j]>lim) break;
            isprime[i*prime[j]]= ture;
            if(i %prime[j]==0) {
                mu[i*prime[j]]=0;
                break;
            }else{
                mu[i*prime[j]]=-mu[i];
            }
        }
    }
}