如果不会线性筛素数的话,建议先看这篇博客了解一下线性筛素数。
莫比乌斯函数函数(积性函数都可以线性筛)主要是在线性筛素数的基础上得到的
我们知道:
若 n=∏i=1npiti
则 μ(n)={(−1)k0k=∑i=1ntiandmax(t1,t2,⋯,tn)≤1others
所以:
1、当 n 是质数时, μ(n)=−1
对于 2和3 设 d=pn 其中 p 为 n 的最小质因子
2、当 p 是 d 的某个质因子时, 则 μ(n)=0
3、当 p 与 d 互质时, μ(n)=−μ(d)
good luck and have fun!!!
附上代码:
int mu[MAXN];
void Mobius(int n)
{
memset(vis,0,sizeof(vis));
mu[1]=1;
prime[0]=0;
for(int i=2;i<=n;i++)
{
if(!vis[i])
{
prime[++prime[0]]=i;
mu[i]=-1;
}
for(int j=1;j<=prime[0]&&i<=n/prime[j];j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
{
mu[i*prime[j]]=0;
break;
}
mu[i*prime[j]]=-mu[i];
}
}
}