也许更好的阅读体验

$前置技能$前置技能

• 学会莫比乌斯函数必须要先知道狄利克雷函数
• 以及什么是逆元（一本正经胡说八道）

  $狄利克雷卷积$狄利克雷卷积

  两个函数 $f,g$f,g
  $\begin{array}{c}{\displaystyle f\ast g\left(n\right)=\sum _{d\mid n}^{n}f\left(d\right)g\left(\frac{n}{d}\right)}\end{array}$f∗g(n)=d∣n∑n​f(d)g(dn​)​
  • 性质
    交换律 $f\ast g=g\ast f$                 f∗g=g∗f
    结合律 $f\ast g\ast h=f\ast (g\ast h)$                 f∗g∗h=f∗(g∗h)
    加法分配率 $f\ast (g+h)=f\ast g+f\ast h$          f∗(g+h)=f∗g+f∗h

  $几个定理$几个定理

  • ①　定义单位函数 $I\left(n\right)=[n=1]$I(n)=[n=1]，即只有当ｎ等于１时， $I\left(1\right)=1$I(1)=1，其余情况都为０
  • ②　 $I\ast f=f$I∗f=f
  • ③　已知函数 $f$f，定义函数 $f$f的逆 $f^{-1}$f−1，满足 $f\ast f^{-1}=I$f∗f−1=I，且积性函数的逆也是积性函数
  • ④　由③可得 $f^{-1}\left(1\right)=\frac{1}{f\left(1\right)}$f−1(1)=f(1)1​
  • ⑤　令 $\xi \left(n\right)=1$ξ(n)=1

$莫比乌斯函数$莫比乌斯函数

• 莫比乌斯函数 $\mu ={\xi }^{-1}$μ=ξ−1
  $n=p_1^{a_1}\cdot p_2^{a_2}\cdot \cdots p_k^{a_k}$n=p1a1​​⋅p2a2​​⋅⋯pkak​​
  $\mu \left(n\right)={\xi }^{-1}\left(n\right)=\{\begin{array}{cc}1& n=1\\ (-1{)}^k& a1=a2=\cdots =ak=1& \\ 0& otherwise\end{array}$μ(n)=ξ−1(n)=⎩⎨⎧​1(−1)k0​n=1a1=a2=⋯=ak=1otherwise​​

$如何推导$如何推导

• $如何求逆$如何求逆

  ③等价于
  
  $\begin{array}{c}{\displaystyle \forall n:\sum _{d\mid n}f\left(d\right)\cdot f^{-1}\left(\frac{n}{d}\right)=[n=1]}\end{array}$∀n:d∣n∑​f(d)⋅f−1(dn​)=[n=1]​
  
  $\begin{array}{c}{\displaystyle \sum _{d\mid n}f\left(d\right)\cdot f^{-1}\left(\frac{n}{d}\right)=I\left(n\right)(n≠1)=0}\end{array}$d∣n∑​f(d)⋅f−1(dn​)=I(n)(n≠​1)=0​
  
  $f^{-1}\left(n\right)\cdot f\left(1\right)=-{\sum }_{d\mid n,d≠1}f\left(d\right)\cdot f^{-1}\left(\frac{n}{d}\right)$f−1(n)⋅f(1)=−∑d∣n,d≠​1​f(d)⋅f−1(dn​)
  
  $\begin{array}{c}{\displaystyle f^{-1}\left(n\right)=\frac{-\sum _{d\mid n,d≠1}f\left(d\right)\cdot f^{-1}\left(\frac{n}{d}\right)}{f\left(1\right)}}\end{array}$f−1(n)=f(1)−∑d∣n,d≠​1​f(d)⋅f−1(dn​)​​

• $莫比乌斯函数$莫比乌斯函数

  令 $f=\xi$f=ξ, $p$p为质数
  
  $f^{-1}\left(1\right)=1$f−1(1)=1
  
  $f^{-1}\left(p\right)=\frac{-f\left(p\right)\cdot f^{-1}\left(1\right)}{f\left(1\right)}=-1$f−1(p)=f(1)−f(p)⋅f−1(1)​=−1
  
  $f^{-1}\left(p^2\right)=-\left(f\right(p^2)\cdot f^{-1}(1)+f(p)\cdot f^{-1}(p\left)\right)=0$f−1(p2)=−(f(p2)⋅f−1(1)+f(p)⋅f−1(p))=0
  
  $f^{-1}\left(p^3\right)=-\left(f\right(p^3)\cdot f^{-1}(1)+f(p^2)\cdot f^{-1}(p)+f(p)\cdot f^{-1}(p^2\left)\right)=0$f−1(p3)=−(f(p3)⋅f−1(1)+f(p2)⋅f−1(p)+f(p)⋅f−1(p2))=0
  
  $\begin{array}{c}{\displaystyle f^{-1}\left(p^k\right)=-\sum _{i=1}^{k}f\left(p^i\right)\cdot f^{-1}\left(p^{k-i}\right)}\end{array}$f−1(pk)=−i=1∑k​f(pi)⋅f−1(pk−i)​
  
  其中只有 $f\left(p^k\right)\cdot f^{-1}\left(1\right)=1,f\left(p^{k-1}\right)\cdot f^{-1}\left(p\right)=-1$f(pk)⋅f−1(1)=1,f(pk−1)⋅f−1(p)=−1，其余项都是0
  
  $f^{-1}\left(p^k\right)=\{\begin{array}{cc}-1& k=1\\ 0& k\>1\end{array}$f−1(pk)={−10​k=1k>1​
  
  $n=p_1^{a_1}\cdot p_2^{a_2}\cdot \cdots p_k^{a_k}$n=p1a1​​⋅p2a2​​⋅⋯pkak​​
  
  所以莫比乌斯函数可以推出来了
  
  $\mu \left(n\right)=f^{-1}\left(n\right)=\{\begin{array}{cc}1& n=1\\ (-1{)}^k& a1=a2=\cdots =ak=1& \Leftarrow 积性函数推出\\ 0& otherwise\end{array}$μ(n)=f−1(n)=⎩⎨⎧​1(−1)k0​n=1a1=a2=⋯=ak=1otherwise​⇐积性函数推出​

$莫比乌斯函数的性质$莫比乌斯函数的性质

• $\mu \ast \xi =I$μ∗ξ=I
  因为 $\mu ={\xi }^{-1}$μ=ξ−1
  所以有 $\begin{array}{c}{\displaystyle \sum _{d\mid n}^n\mu \left(d\right)=\sum _{d\mid n}^n\mu \cdot 1=\mu \ast \xi \left(n\right)=I\left(n\right)=[n=1]}\end{array}$d∣n∑n​μ(d)=d∣n∑n​μ⋅1=μ∗ξ(n)=I(n)=[n=1]​
  记住这句，下面的证明要用到
• $I\ast f=f$I∗f=f
• $f\ast \mu \ast \xi =f$f∗μ∗ξ=f
• $f\ast \xi =g,f=g\ast \mu$f∗ξ=g,f=g∗μ

$线性筛$线性筛

利用积性函数的性质以及 $\mu$μ的表达式

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

$莫比乌斯反演$莫比乌斯反演

• 若有 $\begin{array}{c}{\displaystyle g\left(n\right)=\sum _{d\mid n}f\left(d\right)}\end{array}$g(n)=d∣n∑​f(d)​
  则有 $\begin{array}{c}{\displaystyle f\left(n\right)=\sum _{d\mid n}\mu \left(d\right)g\left(\frac{n}{d}\right)=\sum _{d\mid n}\mu \left(\frac{n}{d}\right)g\left(d\right)}\end{array}$f(n)=d∣n∑​μ(d)g(dn​)=d∣n∑​μ(dn​)g(d)​

  • $证明$证明

    法一 $\begin{array}{c}{\displaystyle \sum _{d\mid n}\mu \left(d\right)g\left(\frac{n}{d}\right)=\sum _{d\mid n}\mu \left(d\right)\sum _{x\mid \frac{n}{d}}f\left(x\right)=\sum _{x\mid n}f\left(x\right)\sum _{d\mid \frac{n}{x}}\mu \left(d\right)=\sum _{x\mid n}f\left(x\right)[\frac{n}{x}=1]=f\left(n\right)}\end{array}$d∣n∑​μ(d)g(dn​)=d∣n∑​μ(d)x∣dn​∑​f(x)=x∣n∑​f(x)d∣xn​∑​μ(d)=x∣n∑​f(x)[xn​=1]=f(n)​
    法二 $g=f\ast \xi ,f=g\ast \mu$g=f∗ξ,f=g∗μ

• 若有 $\begin{array}{c}{\displaystyle g\left(n\right)=\sum _{n\mid d}f\left(d\right)}\end{array}$g(n)=n∣d∑​f(d)​
  则有 $\begin{array}{c}{\displaystyle f\left(n\right)=\sum _{n\mid d}\mu \left(\frac{d}{n}\right)g\left(d\right)}\end{array}$f(n)=n∣d∑​μ(nd​)g(d)​

  • $证明$证明

    $\begin{array}{c}{\displaystyle \sum _{n\mid d}\mu \left(\frac{d}{n}\right)g\left(d\right)=\sum _{k=1}^{+\infty }\mu \left(k\right)g\left(kn\right)=\sum _{k=1}^{+\infty }\mu \left(k\right)\sum _{kn\mid d}f\left(d\right)=\sum _{n\mid d}f\left(d\right)\sum _{k\mid \frac{d}{n}}\mu \left(k\right)=\sum _{n\mid d}f\left(d\right)[\frac{d}{n}=1]=f\left(n\right)}\end{array}$n∣d∑​μ(nd​)g(d)=k=1∑+∞​μ(k)g(kn)=k=1∑+∞​μ(k)kn∣d∑​f(d)=n∣d∑​f(d)k∣nd​∑​μ(k)=n∣d∑​f(d)[nd​=1]=f(n)​

  这一种一般用的比较多

$莫比乌斯反演的应用$莫比乌斯反演的应用

莫比乌斯函数一般用于 $gcd$gcd中
$\begin{array}{cc}{\displaystyle \sum _{i=1}^n\sum _{j=1}^m\gcd (i,j)}& {\displaystyle =\sum _d^{min(n,m)}d\sum _{i=1}^n\sum _{j=1}^m\left[gcd\right(i,j)=d]}\\ {\displaystyle }& {\displaystyle =\sum _d^{min(n,m)}d\sum _{i=1}^{\frac{n}{d}}\sum _{j=1}^{\frac{m}{d}}\left[gcd\right(i,j)=1]}\\ {\displaystyle }& {\displaystyle =\sum _d^{min(n,m)}d\sum _{i=1}^{\frac{n}{d}}\sum _{j=1}^{\frac{m}{d}}\sum _{k\mid gcd(i,j)}\mu \left(k\right)}\\ {\displaystyle }& {\displaystyle =\sum _d^{min(n,m)}d\sum _k^{min(\frac{n}{d},\frac{m}{d})}\mu \left(k\right)\sum _{k\mid i}^{\frac{n}{d}}\sum _{k\mid j}^{\frac{m}{d}}}\\ {\displaystyle }& {\displaystyle =\sum _d^{min(n,m)}d\sum _k^{min(\frac{n}{d},\frac{m}{d})}\mu \left(k\right)\lfloor \frac{n}{kd}\rfloor \lfloor \frac{m}{kd}\rfloor }\end{array}$i=1∑n​j=1∑m​gcd(i,j)​=d∑min(n,m)​di=1∑n​j=1∑m​[gcd(i,j)=d]=d∑min(n,m)​di=1∑dn​​j=1∑dm​​[gcd(i,j)=1]=d∑min(n,m)​di=1∑dn​​j=1∑dm​​k∣gcd(i,j)∑​μ(k)=d∑min(n,m)​dk∑min(dn​,dm​)​μ(k)k∣i∑dn​​k∣j∑dm​​=d∑min(n,m)​dk∑min(dn​,dm​)​μ(k)⌊kdn​⌋⌊kdm​⌋​
令 $T=kd$T=kd
$\begin{array}{c}{\displaystyle =\sum _T^{min(n,m)}\lfloor \frac{n}{T}\rfloor \lfloor \frac{m}{T}\rfloor \sum _{k\mid T}\frac{T}{k}\mu \left(k\right)}\end{array}$                            =T∑min(n,m)​⌊Tn​⌋⌊Tm​⌋k∣T∑​kT​μ(k)​
以上是莫比乌斯反演推出来的式子

$\begin{array}{c}{\displaystyle =\sum _T^{min(n,m)}\lfloor \frac{n}{T}\rfloor \lfloor \frac{m}{T}\rfloor \phi \left(T\right)}\end{array}$                            =T∑min(n,m)​⌊Tn​⌋⌊Tm​⌋φ(T)​
这一步是欧拉反演，证明请移步欧拉函数|(扩展)欧拉定理|欧拉反演
当然，这里这个例子不如直接用欧拉反演
$\begin{array}{cc}{\displaystyle \sum _{i=1}^n\sum _{j=1}^m\gcd (i,j)}& {\displaystyle =\sum _{i=1}^n\sum _{j=1}^m\sum _{d\mid gcd(i,j)}\phi \left(d\right)=\sum _{d=1}^{min(n,m)}\lfloor \frac{n}{d}\rfloor \lfloor \frac{m}{d}\rfloor \phi \left(d\right)}\end{array}$i=1∑n​j=1∑m​gcd(i,j)​=i=1∑n​j=1∑m​d∣gcd(i,j)∑​φ(d)=d=1∑min(n,m)​⌊dn​⌋⌊dm​⌋φ(d)​

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧