莫比乌斯反演

• 莫比乌斯函数如下 $$mu(d)= begin{cases} 1 &mbox{d=1}\ (-1)^k &mbox{$d=p_1p_2p_3...p_k,p_i$是互异素数}\ 0 &mbox{其余情况} end{cases}$$
• 于是有如下两条性质
  $sum_{d|n}^{}{mu(d)=[n=1]}$
  $sum_{d|n}^{}{frac {mu(d)}{d}}={frac {phi(n)}{n}}$
• 第一个性质用组合数可以很方便得到
• 莫比乌斯反演如下
  如果有
  $f(n)=sum_{d|n}^{}{g(d)}$
  那么
  $g(n)=sum_{d|n}^{}{mu(d)cdot f(frac nd)}$
• $sum_{d|n}^{}{mu(d)cdot f(frac nd)}=sum_{d|n}^{}{mu(d)cdot sum_{k| frac nd}^{}g(k)}$
• $=sum_{d|n}^{}{sum_{k| frac nd}^{}{mu(d) cdot g(k)}}$
• 显然其实就是枚举$dcdot k|n$
• 即$=sum_{k|n}^{}{sum_{d| frac nk}^{}{mu(d) cdot g(k)}}$
• 由性质1可得该式$=g(n)$
• (其实我每次都没构造函数,我直接推的2333…)
• 上一段线筛莫比乌斯函数代码
  

  1 2 3 4 5 6 7 8 9 10 11

  void (int n){ mu[1]=1; for(int i=2;i<=n;++i){ if(!vis[i])mu[i]=-1,p[++cnt]=i; for(int j=1;j<=cnt&&i<=n/p[j];++j){ vis[i*p[j]]=1; if(i%p[j]==0)break; mu[i*p[j]]-=mu[i]; } } }