莫比乌斯函数的线性筛

· · 个人记录 

void getmu(int x){
    vis[1]=1;
    mu[1]=1;
    for(int i=2;i<=x;i++){
        if(!vis[i]){
            prime[++cnt]=i,mu[i]=-1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=x;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j] is 0){
                mu[i*prime[j]]=0;break;
            }
            else mu[i*prime[j]]=-mu[i];
        }
    }
}

重要公式：

\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1] =\sum_{d=1}^{n} \mu(d)\left \lfloor n/d \right \rfloor\left \lfloor m/d \right \rfloor \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k] =\sum_{i=1}^{\left \lfloor n/d \right \rfloor}\sum_{j=1}^{\left \lfloor m/d \right \rfloor}[gcd(i,j)=1]