推荐讲义
(g(x)=sumlimits_{d|x}f(d) iff f(x)=sumlimits_{d|x}mu(frac{x}{d})*g(d))
(g(x)=sumlimits_{x|d}^nf(d) iff f(x)=sumlimits_{x|d}^nmu(frac{d}{x})*g(d))
(mu)为莫比乌斯函数。
定义：(sumlimits_{d|x}mu(d)=[x==1])
经分析可得：
①(x=p_1p_2p_3...p_n,mu(x)=(-1)^n)
②(x=p^2*d,mu(x)=0)
③(x=1,mu(x)=1)
(mu)的线性筛代码
mu[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i])prime[++prime[0]]=i,mu[i]=-1;
for(int j=1;j<=prime[0]&&1ll*i*prime[j]<=n;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0)break;
mu[i*prime[j]]=-mu[i];
}
}