断断续续学习了好久的莫比乌斯反演，因为涉及到许多数论知识，所以想写一篇总结，统合一下相关知识点。
部分内容选自oi-wiki
前置知识
积性函数
定义
若$gcd(x,y)=1$，并且$f(x*y)=f(x)*f(y)$，则函数$f(x)$为积性函数。
举例
常函数：$I(n)=1$
单位函数：$varepsilon (n)=[n=1]$
欧拉函数：$varphi (n) = sum_{1}^{n}[gcd(i,n)==1]$
(当然，还有很多数论函数也都是积性函数，但在莫比乌斯反演中这三个是较为重要的)
狄利克雷卷积
定义
两个数论函数$f(n),g(n)$的迪利克雷卷积为
$egin{equation} (f*g)(n)=sum_{d mid n}f(d)*g(frac{n}{d}) end{equation}$
当然$(f*g)(n)$也是数论函数
性质
1 .狄利克雷卷积满足交换律。
$f*g=g*f$
2 狄利克雷卷积满足结合律。
$((f*g)*h)(n)=(f*(g*h))(n)$
证明
$((f*g)*h)(n)=sum_{d mid n}(f*g)(d)*h(frac{n}{d})$
$((f*g)*h)(n)=sum_{d mid n}h(frac{n}{d})sum_{d1 mid d}f(d1)g(frac{d}{d1})$
$((f*g)*h)(n)=sum_{a*b=n}h(a)sum_{c*d=b}f(c)g(d))$
$((f*g)*h)(n)=sum_{a*c*d=n}h(a)f(c)g(d))=(f*(g*h))(n)$
2 .$varepsilon$为狄利克雷卷积的单位元，即任何数论函数与$varepsilon (x)$的卷积都为本身.。
证明
$(f* varepsilon)(n)=sum_{d mid n}f(d)* varepsilon(frac{n}{d})$
$ecause varepsilon(n)=[n=1]$
$ herefore (f* varepsilon)(n)=f(n)$
狄利克雷卷积的逆函数
定义
若存在
$(f*g)(n)= varepsilon (n)$
则称$g(n)$为$f(n)$的逆函数，记作$f^{-1}(n)$
性质
1.积性函数的逆函数也为积性函数。
证明
设$f(n)$为积性函数，则
$f(i*j)*f^{-1}(i*j)= varepsilon$
$f(i)*f^{-1}(i)*f(j)*f^{-1}(j)= varepsilonquad (varepsilon * varepsilon = varepsilon )$
联立两式可以知道
$f(i*j)*f^{-1}(i*j)=f(i)*f^{-1}(i)*f(j)*f^{-1}(j)$
$f^{-1}(i*j)=f^{-1}(i)*f^{-1}(j)$
推导
常函数$I(n)=1$
推导常函数的逆函数$I^{-1}(n)$
$I^{-1}(n)*I(n)= varepsilon$
$sum_{d mid n}I(d)*I^{-1}(frac{n}{d})= varepsilon $
当$n=1$时
$I^{-1}(1)=frac{1}{I(1)}=1$
当$n!=1$时
$sum_{d mid n}I(d)*I^{-1}(frac{n}{d})=0$
$I(1)*I^{-1}(n)+sum_{d mid n && d!=1}I(d)*I^{-1}(frac{n}{d})=0$
$I^{-1}(n)=frac{-sum_{dmid n && d!=1}quad I(d)*I^{-1}(frac{n}{d})}{f(1)}$
这就是$I^{-1}$的式子了
我们带入一个素数$p$进行计算
$I^{-1}(p)=frac{-I(n)*I^{-1}(1)}{I(1)}=-1$
带入$p^{2}$
$I^{-1}(p^{2})=frac{-(I(p)*I^{-1}(p)+I(p^{2})*I^{-1}(1))}{I(1)}=0$
同理，推广到$p^{3}...p^{4}$
$I^{-1}(p^{k})=0$
则我们随便选一个合数$T$，将$T$分解质因子
$T=prod_{i}^{n}p_{i}^{k_{i}}$
因为积性函数的逆函数也是积性函数，所以
$I^{-1}(T)=prod_{i}^{n}I^{-1}(p_{i}^{k_{i}})$
此处如果有$k_{i}>1$，则$I^{-1}(T)=0$
否则$I^{-1}(T)=(-1)^{n}$
$I^{-1}(n)= egin{cases}1 & n=1\ 0 & n含有某平方因子\ -1^{k} &k为n本质不同的质因子个数 end{cases}$
$I^{-1}(n)$还有一个名字：莫比乌斯函数
莫比乌斯函数
定义
定义莫比乌斯函数$u(u=I^{-1})$，则
$u(n)= egin{cases}1 & n=1\ 0 & n含有某平方因子\ -1^{k} &k为n本质不同的质因子个数 end{cases}$
性质
$sum_{d mid n}u(n)=left{egin{matrix} 1& n=1\ 0& n!=1end{matrix} ight. $
证明
$u*I=varepsilon$
$sum_{dmid n}u(d)I(frac{n}{d})=varepsilon(n)$
$sum_{dmid n}u(d)=varepsilon(n)$
性质扩展
$sum_{i=1}^{n}sum_{j=1}^{m}[gcd(i,j)=1]=sum_{i=1}^{n}sum_{j=1}^{m}sum_{d mid gcd(i,j)}u(d)$
证明
$[gcd(i,j)=1] = varepsilon (gcd(i,j))\ [gcd(i,j)=1]= sum_{d mid gcd(i,j)}u(d)$
线性筛法求莫比乌斯函数
通过莫比乌斯函数的通式可以得知，一个素数的莫比乌斯函数值为-1，一个没有平方因子的合数的莫比乌斯函数值为0，那么可以根据定义筛出莫比乌斯函数值。
1 void init(int n) { 2 int len = 0; 3 u[1] = 1; 4 for (int i = 2; i <= n; i++) { 5 if (!vis[i]) 6 pri[++len] = i, u[i] = -1; 7 for (int j = 1; j <= len && i * pri[j] <= n; j++) { 8 vis[i * pri[j]] = 1; 9 if (i % pri[j] == 0) 10 break; 11 else u[i * pri[j]] = -u[i]; 12 } 13 } 14 }
稍微解释一下为什么可以筛出莫比乌斯函数，线性筛在标记合数时，是在合数p的最小质因数x和p/x时标记该合数的。此时可以通过判断p/x是否整除x来确定该合数有无平方因子。
莫比乌斯反演
终于到重头戏了，其实经过上面的前置知识，已经或多或少的了解过莫比乌斯反演了。
定义
设两个数论函数为$f(n),g(n)$，若满足
$f(n) = sum_{d mid n}g(d)$
那么有
$g(n)=sum_{d mid n}u(d)f(frac{n}{d})$
这就是莫比乌斯反演的公式
证明
原式可看成
$f(n) = sum_{d mid n}g(d)*I(frac{n}{d})quad quad(f=g*I)$
则
$egin{aligned}f*u & =g*I*u \ f*u &= g* varepsilon \ f*u&=gend{aligned}$