莫比乌斯函数 $$u(d)= \left\{ {\begin{array}{}1 \ (d=1)\\(-1)^k\ (d=p_1\times p_2\times p_3 \cdots \times p_k) \\0\ (other)\end{array}} \right .$$
其中,$\forall {p_i,pj}$满足$gcd(p_i,p_j)=1$。且$\forall p_i$都是质数。
性质$1$：$ \sum_{d|n} u(d)= \left\{ {\begin{array}{} 1\ (n=1)\\0\ (n>1) \end{array}} \right .$ 证明： $n>1$时，$d$质因数分解后质因数个数一定大于$1$
因为当$n$有多个相同的质因数时，$u(d)=0$，于是不考虑这种情况，现在$d=1$或$d=p_1\times p_2 \cdots p_k$
设$g(i)= \left\{ {\begin{array}{} u(1)\ (i=0)\\u(p_1\times p_2\cdots p_i)\ (i>0) \end{array}} \right .$
那么$$ \sum_{d|n} u(d) = \sum_{i=0}^k C_k^ig(i) $$
$k$是$n$的质因数中不同的质数的个数。
那么$C_k^i$的含义就是，从这些不同的质数中选$i$个出来的总方案数，$g(i)$的含义就是，$i=0$没有任何一个质数时，就是$u(1)$，如果有，那么就是$(-1)^i$，那么对于$i$相同的$d$的数量，就是$C_n^i$。
很容易发现，$\sum_{i=0}^k C_k^ig(i)$可以看做是：
$C_k^0g(0)+C_k^1g(1)+C_k^2g(2)\cdots+C_k^kg(k)$
二项式定理！
$$\sum_{i=0}^k C_k^ig(i)=C_k^0\times 1+C_k^1(-1)^1+C_k^2(-1)^2\cdots C_k^k(-1)^k$$
$$=(1+(-1))^k=0^k$$
当$k=0$的时候，$0^0$无意义，但是由于$0$时的函数$g$并不是$(-1)^i$，所以$0$的时候是$g(0)=1$，其他情况是$0$
证明完毕。
性质2: $\sum_{d|n}\frac{u(d)}{d}=\frac{\varphi(n)}{n}$ 其中，$\varphi(n)$，欧拉函数，含义是小于$n$大于$0$的数里面有多少个数与$n$互质。
$$\sum_{d|n}\frac{u(d)}{d}=\frac{\varphi(n)}{n}$$$$n\sum_{d|n}\frac{u(d)}{d}=\varphi(n)$$$$n\sum_{d|n}\frac{\frac{n}{d}u(d)}{n}=\varphi(n)$$$$\sum_{d|n}\frac{n}{d}u(d)=\varphi(n)$$
可以模拟来理解，$\sum_{d|n}\frac{n}{d}u(d) $是一个容斥函数。筛去含$d$质因数的数字，然后做容斥得到不含有$n$的任何一个质因数的数个数。
证明完毕
莫比乌斯反演 切入正题。
如果有：
$$F(n)=\sum_{d|n}f(d)$$
则有：
$$f(n)=\sum_{d|n}u(d)F(\frac{n}{d})$$
证明：
$$\sum_{d|n}u(d)F(\frac{n}{d})=\sum_{d|n}u(d)\sum_{d'|\frac{n}{d}}f(d')$$
方法$1$，容斥。
由等式的含义可以得到：
$$\sum_{d|n}u(d)\sum_{d'|\frac{n}{d}}f(d')=\sum_{i=0}^k\sum_{j=0}^iC_i^j(-1)^jf(n-i)$$
可以通过之前证明性质$2$时的方法，也可以通过杨辉三角。
只有$i=0$时，才会让$\sum_{j=0}^iC_i^j(-1)^j$=1 ，其他情况为$0$。
$$\sum_{i=0}^k\sum_{j=0}^iC_i^j(-1)^jf(n-i)=f(n)$$
方法$2$，通过循环下手。
$$\sum_{d|n}u(d)\sum_{d'|\frac{n}{d}}f(d')=\sum_{d'|n}f(d')\sum_{d|\frac{n}{d'}}u(d)$$
通过之前的性质，只有在$\frac{n}{d'}=1$时，$\sum_{d|\frac{n}{d'}}u(d)$才等于$1$，其他情况为$0$。
所以
$$\sum_{d'|n}f(d')\sum_{d|\frac{n}{d'}}u(d)=f(n)$$
证明完毕。
莫比乌斯表达式也可以是：$$F(n)=\sum_{n|d}f(d)\Rightarrow f(n)=\sum_{n|d}u(\frac{d}{n})F(d)$$
常用题型 1 求出$1\le i \le n,1\le j\le m$中$gcd(i,j)$的和。
$$ans=\sum_{i=1}^n\sum_{j=1}^mgcd(i,j)$$
常用套路，把$gcd$给提出来。
$$ans=\sum_{d=1}^{min(n,m)}d\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==d]$$
$[gcd(i,j)==d]$的意思是括号内容成立为$1$，不成立为$0$。
那么设$g(d)=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==d]$，设$f(k)=n/k\times m/k$
$/$是向下取整。
明显有
$$f(n)=\sum_{n|d}g(d)$$
则可以进行反演了：
$$g(d)=\sum_{d|k}u(\frac{k}{d})f(k)=\sum_{d|k}u(\frac{k}{d})\times n/k\times m/k$$
2 求出$1\le i\le n$和$1 \le j \le m$中$gcd(i,j)$为质数的数量。
首先设$g(x)$为$gcd(i,j)=x$的数量函数。
设$F(d)=\frac{n}{d}\times\frac{m}{d}$，含义就是满足$d|gcd(i,j)$的数量。
$$F(n)=\sum_{n|d}g(d)$$
$$g(x)=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=x]$$
反演后：
$$g(i)=\sum_{i|d}u(\frac{d}{i})F(d)=\sum_{i|d}u(\frac{d}{i})\frac{n}{d}\times\frac{m}{d}$$
同样是反演和容斥原理。
接下来进行优化：切换枚举顺序
$$ans=\sum_i\sum_{i|d}u(\frac{d}{i})\frac{n}{d}\times\frac{m}{d}=\sum_d\frac{n}{d}\times\frac{n}{d}\sum_{i|d}u(\frac{d}{i})$$
那么预处理出每个$d$的$\sum_{i|d}u(\frac{d}i)$。可以降低复杂度，避免循环过多。
而预处理也是十分精妙，可以直接整合到线性筛求莫比乌斯函数的过程中：
设$$s(d)=\sum_{i|d}u(\frac{d}i)$$ 我们在线性筛转移时，如果$i\%prime[j]\ne 0$,则$s[i\times prime[j]]=u[i]-s[i]$，否则，$s[i\times prime[j]]=u[i]$
证明很简单，$s(d)$函数的含义就是，如何$d$有$k$个完全不相同质因数，则我的值为$(-1)^{k-1}\times k$。否则，$k$只有在仅有两个相同的质因数时有值，值就是$(-1)^{k-1}$。
当$d\%prime[j]\ne0$时
$$u(d)-s(d)=(-1)^k-k(-1)^{k-1}=(-1-k)(-1)^{k-1}$$$$=-1(k+1)(-1)^{k-1}=(k+1)(-1)^{k}=s(d\times prime[j])$$
如果$d\%prime[j]=0$，如果$d$已经含有多个相同质因数，$u(d)=0$，所以这种情况不影响。所以我们只讨论$d$现在没有多个相同质因数的情况。
$d'=d\times prime[j]$，$d'$有两个相同质因数，只有在刚好$\sum_{i|d}u(\frac{d}i)$的$i=prime[j]$时，才有值。
故$s(d')=(-1)^{k}=u(d)$
所以在线性筛时直接算出$s(d)$就可以了。
最后答案是（还可以再$n/d$上做前缀和优化，但是与本文内容不大相关，不在此展开）
$$ans=\sum_d\frac{n}{d}\times\frac{n}{d}s(d)$$