莫比乌斯反演
引入
莫比乌斯反演用处：对于一些函数 \(f(n)\)，如果比较难以求出它的值，但容易求出其倍数和或约束和 \(g(n)\)，则可以通过莫比乌斯反演简化运算。
莫尼乌斯函数
定义
定义 \(\mu\) 为莫比乌斯函数，
详细解释一下后两条，我们令 \(n=\prod_{i=1}^{k}p_i^{c_i}\)，也就是将 \(n\) 分解质因数，\(p_i\) 为质因子，\(c_i\ge 1\)，则凡是有 \(c_i>1\)，\(\mu(n) = 0\)，而当任意的 \(c_i\) 都等于 \(1\)，\(\mu(n) = (-1) ^ k\)。
性质
证明
既然 \(n=\prod_{i=1}^{k}p_i^{c_i}\) ，那么我们令 \(d = \prod_{i=1}^k p_i^{\beta_i}\)，其中 \(0 \le \beta_i \le c_i\)
对于存在 \(\beta_i>=2\) 的情况，\(\mu(d)=0\)，我们可以不管。
对于所有 \(\beta_i\) 都小于等于 1 的情况，很显然我们按照\(\beta_i=1\)有几个给它分一下组，也就是按照选了几个质因数给它分组，这样，很显然 \(\mu(d)\) 的值是 \(\C_{k}^0\times(-1)^0 + \C_{k}^1\times(-1)^1+\cdots+\C_{k}^k\times(-1)^k\) 也就是 \(\sum_{i=0}^k\C_k^i\times(-1)^i\)
看到这个形式，我们可以想起来二项式定理：
我们可以令 \(a=1,b=-1\)，代入二项式定理正好就是我们刚才推出的式子。
所以
莫比乌斯反演
形式一
定义在正整数域上的两个函数，若
则
莫比乌斯反演相关的题都是去套用这个定理来简化 \(f(n)\) 的计算。
证明
首先将 第一个式子代入第二个式子，消去 \(F(n)\):
这其实就相当于一个二重循环：
for d|n
for i|(n/d)
sum += mu(d) * f(i)
考虑将循环顺序颠倒，没有影响，\(i\) 可遍历到 \(n\) 的任何因数。
再考虑对于 \(\mu(n)\) 的遍历，既然 \(i|\frac nd\)，那么 \(di|n\)，那么 \(d|\frac ni\)
则：
前面已经证明过 \(\sum_{d|n}\mu(d) = \begin{cases} 1 &n=1\\ 0 & n \ne1 \end{cases}\)，则当只有 \(\frac ni = 1\) 时才会对答案有贡献，其他时候都是 0，则 \(i=n\) 时，答案为 \(f(n)\)，证毕。
形式二
我们一般会用到莫比乌斯反演的另外一种形式：
证明
形式二的证明与形式一略有不同，但是大致一样。
首先依旧是将第一个式子代入第二个式子。
设 \(d'=\frac dn\)，\(d = d'n\)，因为 \(d|i\)，所以 \(d'n|i\)，所以 \(d'|\frac in\)
与前面同理，\(\mu(n)\) 只有在 \(n=1\) 时才是 1，所以最终答案为 \(f(n)\).
例题
VLATTICE - Visible Lattice Points
(太懒了懒得写了回头补