莫比乌斯反演
引入
莫比乌斯反演用处：对于一些函数 \(f(n)\)，如果比较难以求出它的值，但容易求出其倍数和或约束和 \(g(n)\)，则可以通过莫比乌斯反演简化运算。
莫尼乌斯函数
定义
定义 \(\mu\) 为莫比乌斯函数，
\[\mu(n) = \begin{cases} 1 & n=1\\ 0& n含平方因子\\ (-1)^k & k为n的本质不同质因子个数\\ \end{cases} \]详细解释一下后两条，我们令 \(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\)。
性质
\[\sum_{d|n}\mu(d) = \begin{cases} 1 &n=1\\ 0 & n \ne1 \end{cases} \]证明
既然 \(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+b)^k=\C_k^0a^kb^0+\C_k^1a^{k-1}b^1+\cdots+\C_k^ka^0b^k \]我们可以令 \(a=1,b=-1\)，代入二项式定理正好就是我们刚才推出的式子。
所以
\[\sum_{d|n} \mu(d) = \sum_{i=0}^k\C_k^i\times(-1)^i=(1-1)^k=0 \]莫比乌斯反演
形式一
定义在正整数域上的两个函数，若
\[F(n) = \sum_{d|n}f(d) \]则
\[f(n) = \sum_{d|n}\mu(d)F(\frac nd) \]莫比乌斯反演相关的题都是去套用这个定理来简化 \(f(n)\) 的计算。
证明
首先将 第一个式子代入第二个式子，消去 \(F(n)\):
\[\sum_{d|n}\mu(d)F(\frac nd)=\sum_{d|n}\mu(d)\sum_{i|\frac nd}f(i) \\ \]这其实就相当于一个二重循环：
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)F(\frac nd)=\sum_{d|n}\mu(d)\sum_{i|\frac nd}f(i) \\=\sum_{i|n}f(i)\sum_{d|\frac ni}\mu(d) \]前面已经证明过 \(\sum_{d|n}\mu(d) = \begin{cases} 1 &n=1\\ 0 & n \ne1 \end{cases}\)，则当只有 \(\frac ni = 1\) 时才会对答案有贡献，其他时候都是 0，则 \(i=n\) 时，答案为 \(f(n)\)，证毕。
形式二
我们一般会用到莫比乌斯反演的另外一种形式：
\[若 F(n) = \sum_{n|d}f(d)\\ 则 f(n) = \sum_{n|d}\mu(\frac dn) F(d) \]证明
形式二的证明与形式一略有不同，但是大致一样。
首先依旧是将第一个式子代入第二个式子。
\[\sum_{n|d}\mu(\frac dn) F(d) = \sum_{n|d}\mu(\frac dn)\sum_{d|i}f(i) \]设 \(d'=\frac dn\)，\(d = d'n\)，因为 \(d|i\)，所以 \(d'n|i\)，所以 \(d'|\frac in\)
\[\sum_{n|d}\mu(\frac dn) F(d) = \sum_{n|d}\mu(\frac dn)\sum_{d|i}f(i) \\ = \sum_{n|i}f(i)\sum_{d'|\frac in} \mu(d') \]与前面同理，\(\mu(n)\) 只有在 \(n=1\) 时才是 1，所以最终答案为 \(f(n)\).
例题
VLATTICE - Visible Lattice Points
(太懒了懒得写了回头补
标签：frac,乌斯,sum,mu,反演,莫比 From： https://www.cnblogs.com/djc01/p/17253225.html