莫比乌斯反演
前置知识：数论分块
莫比乌斯函数
定义莫比乌斯函数\(\mu (x)\)，如果\(x\)的某个质因数出现超过一次，则\(\mu(x)=0\),否则\(\mu(x)=(-1)^k\),其中\(k\)是\(n\)的本质不同的质因子个数。
形式化地，
\[\mu(x)= \cases{ 1~~~~~~~~~~~~~~~~~n=1\\ (-1)^k ~~~~~~~~~{n=p_1p_2\cdots p_k}\\ 0 ~ ~ ~~~~~~~~~~~~~~~ other } \]其中\(p_i\)为不同的质数。DDD
莫比乌斯函数是积性函数，并且有一个重要性质是：\(\sum_{d|n}\mu(d)=\cases{1,~~~~n=1\\0,~~~~n>1}\)
证明：\(\sum_{d|n}\mu(d)\)其实等价于\(\sum_{i=0}^{k}C_k^i(-1)^k\)，相当于在\(k\)个质因数中选出\(i\)个，每一种\(i\)的答案的和。
莫比乌斯反演
设\(g(n)\)和\(f(n)\)是定义在非负整数集合上的两个函数，并且满足\(g(n)=\sum_{d|n}f(d)\)，那么
\[f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d}) \]证明：
\[\begin{aligned} &\sum_{d|n}\mu(d)g(\frac{n}{d})\\ =& \sum_{d|n}\mu(d)\sum_{k|\frac{n}{d}}f(k)\\ =& \sum_{d|n}\sum_{k|\frac{n}{d}}f(k)\mu(d)\\ =& \sum_{k|n}\sum_{d|\frac{n}{k}}f(k)\mu(d)\\ =&\sum_{k|n}f(k)\sum_{d|\frac{n}{k}}\mu(d)\\ =& f(n) \end{aligned} \]莫比乌斯反演还有另外一种形式:如果\(f(n)=\sum_{n|d}g(d)\)，那么
\[g(n)=\sum_{n|d}\mu(\frac{d}{n})f(d) \]几种常见的莫比乌斯反演
上面的式子中 取\(f(n)=\mu(n)\)，则有\(g(n)=\sum_{d|n}f(d)\)，满足莫比乌斯反演的条件，可以进行反演,\(f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})=\mu(n)\)
欧拉函数\(\phi(n)\)的一个性质是：\(n=\sum_{d|n}\phi(d)\)。带入\(f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})\)得
\[\phi(n)=\sum_{d|n}\mu(d)\frac{n}{d} \]\(\mu(n)\)是个积性函数，可以用线性筛预处理出来。
例题：
1.求\([1,n]\)和\([1,m]\)上互质的数的个数
\[\begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==1]\\ =&\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\mu(d)\\ =&\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|i \&d|j}\mu(d)\\ =&\sum_{d=1}^{min(n,m)}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}1\\ =&\sum_{d=1}^{min(n,m)}\mu(d)\times\lfloor\frac{n}{d}\rfloor\times\lfloor\frac{m}{d}\rfloor \end{aligned} \]然后数论分块求解就行哩