线性筛-mobius，强大O(n)

首先，你要知道什么是莫比乌斯函数

然后，你要知道什么是积性函数

最后，你最好知道什么是线性筛

莫比乌斯反演

积性函数

线性筛，见上一篇

知道了，就可以愉快的写mobius函数了

由定义：

μ(n)= 1 (n=1)

(-1)^k (n=p1p2...pk) /* 注意质因子次数为1因为次数大于等于2则含有平方因子 */

0 (其他)

为什么关系平方因子呢？

因为，由定义：

/*

莫比乌斯函数完整定义的通俗表达：

1）莫比乌斯函数μ(n)的定义域是N

2）μ(1)=1

3）当n存在平方因子时，μ(n)=0

4）当n是素数，μ(n)=-1

5）当n是奇数个不同素数之积时，μ(n)=-1

6）当n是偶数个不同素数之积时，μ(n)=1

*/

Hint

由μ函数本身的积性

所以对于其他情况，只需要O(1)的从 mu[i] -> mu[i*p[j]] 就可以了

mu[i*p[j]]=-mu[i];

综上所述：

const int maxn=+;

int mu[maxn],p[maxn],flag[maxn],cnt;

void mobius(int n){

  mu[]=;

  for(int i=;i<=n;i++){

    if(!flag[i])p[++cnt]=i,mu[i]=-;

    for(int j=;j<=cnt && i*p[j]<=n;j++){

      flag[i*p[j]]=;

      if(i%p[j]==){mu[i*p[j]]=;break;}

      mu[i*p[j]]=-mu[i];

    }

  }

}

mobius

巴特西

线性筛-mobius，强大O(n)

最新文章

热门文章