设函数$\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}$$spa
若是code
$g\left( n\right) =\sum _{d|n }f\left( d\right)$blog
那么input
$f\left( n\right) =\sum _{d|n}\mu \left( d\right) g\left( \dfrac {n}{d}\right)$string
$$\sum _{d|n}\mu \left( d\right) g\left( \dfrac {n}{d}\right)$$io
$$=\sum _{d|n}\mu \left( \dfrac {n}{d}\right) g\left( d\right)$$class
$$=\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) $$im
$$=\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; }