莫比乌斯函数

luckydrawbox · 2021-08-27 23:01:04 · 个人记录

莫比乌斯函数，记作 \mu(N)。

• 当 N 包含相等的质因子时，\mu(N)=0。
• 当 N 的所有质因子各不相等且 N 有偶数个质因子时，\mu(N)=1。
• 当 N 的所有质因子各不相等且 N 有奇数个质因子时，\mu(N)=-1。

求 1\sim N 的莫比乌斯函数

int miu[N];
bool v[N];
void Mobius(int n){
    for(int i=1;i<=n;i++)
        miu[i]=1,v[i]=0;
    for(int i=2;i<=n;i++)
        if(!v[i]){
             miu[i]=-1;
             for(int j=2*i;j<=n;j+=i)
                 v[j]=1,miu[i]*=-1*((j/i)%i!=0);
         }
}

时间复杂度 O(n\log\log n)。