设函数\mu(n)为莫比乌斯函数
\mu =\begin{cases}\left( -1\right) ^{k}\left( n=p_{1}p_{2}\ldots p_{k}\right) \\ O\left( \exists P^{2}|n\right) \\ 1\left( n=1\right) \end{cases}
如果
g\left( n\right) =\sum _{d|n }f\left( d\right)
那么
f\left( n\right) =\sum _{d|n}\mu \left( d\right) g\left( \dfrac {n}{d}\right)
\sum _{d|n}\mu \left( d\right) g\left( \dfrac {n}{d}\right)
=\sum _{d|n}\mu \left( \dfrac {n}{d}\right) g\left( d\right)
=\sum _{d|n}\mu \left( \dfrac {n}{d}\right) \sum _{k|d}f\left( k\right)
=\sum _{k|n}\sum_{d|{\dfrac{n}{k}}}\mu(d)f(k)
=\sum _{k|n}[\dfrac{n}{k}=1]f(k)
=f(n)
因为\mu(n)为积性函数
那么可以利用线性筛来计算
#include<cstdio>
#include<cstring>
const int MAXN=1e6+10;
int prime[MAXN],mu[MAXN],vis[MAXN],tot,n;
void Euler()
{
vis[1]=1;mu[1]=1;
for(int i=2;i<=n;i++)
{
if(!vis[i]) prime[++tot]=i,mu[i]=-1;//只有一个质因子
for(int j=1;i*prime[j]<=n&&j<=tot;j++)
{
vis[ i*prime[j] ]=1;
if(i%prime[j]==0)//i中包含prime[j]
{
mu[ i*prime[j] ]=0;//乘起来之后肯定包含prime[j]^2
break;
}
else mu[ i*prime[j] ]=-mu[i];//多了一个质因子
}
}
}
int main()
{
printf("Please input number:\n");
scanf("%d",&n);
Euler();
printf("%d",mu[n]);
return 0;
}