莫比乌斯反演的相关概念

莫比乌斯函数的定义： 莫比乌斯函数是一个定义在正整数域上的一个函数，记作 $\mu{(x)}$。我们先将 $x$ 进行质因数分解 $x=p_1^{\alpha_1}p_2^{\alpha_2}…p_k^{\alpha_k}$，其中 $p_i$ 均为质数，$\alpha_i \geq 1$。则莫比乌斯函数的具体定义如下：

$$ \mu{(x)} = \begin{cases} \exists \alpha_i \geq 2,~\mu{(x)}=0 \newline \forall \alpha_i =1,~\mu{(x)}=(-1)^k \end{cases} $$

特别地，我们规定 $1$ 没有质数，也就是对于 $1$ 进行质因数分解后 $k$ 为 $0$，因此 $\mu{(1)}=1$

莫比乌斯函数的性质： 我们定义 $S(n)=\sum_{d\vert n} \mu{(d)}$，也就是 $n$ 的所有约数的莫比乌斯函数的和。那么 $S(n)$ 一定存在如下性质：

$$ S(n)= \begin{cases} 1,~n=1 \newline 0,~n>1 \end{cases} $$

我们可以证明一下当 $n>1$ 时为什么 $S(n)=0$，假设此时 $n=p_1^{\alpha_1}p_2^{\alpha_2}…p_k^{\alpha_k}$，由于 $n>1$，所以此时 $n$ 至少包含一个质因子，即 $k \geq 1$。

此时对于 $n$ 的任意一个约数 $d=p_1^{\beta_1}p_2^{\beta_2}…p_k^{\beta_3},~0\leq \beta_i \leq \alpha_i$，如果某一个 $p_i$ 的次数 $\beta_i \geq 2$，那么这个 $d$ 的莫比乌斯函数就是 $0$，我们先将所有莫比乌斯函数为 $0$ 的约数都忽略。

此时剩下的所有约数 $d$ 的 $\beta_i$ 不是 $0$ 就是 $1$。这意味着 $\beta_1 \sim \beta_k$ 不是取 $1$ 就是取 $0$，而 $d$ 的莫比乌斯函数 $\mu{(d)}$ 的取值就取决于有多少个 $\beta_i$ 取 $1$，如果有 $m$ 个 $\beta_i$ 取 $1$，那么 $\mu{(d)}= (-1)^m$。

那么此时这 $k$ 个 $\beta_i$ 一共有 $k+1$ 种方案，第一种是 $k$ 个数中有 $0$ 个 $1$，此时他们的贡献应该是 $C_k^0(-1)^0$，第二种是 $k$ 个数中有 $1$ 个 $1$，此时他们的贡献应该是 $C_k^1(-1)^1$，以此类推。因此 $n$ 的所有约数 $d$ 的莫比乌斯函数的和也就是 $S(n)$ 就应该是 $C_k^0(-1)^0+C_k^1(-1)^1+…+C_k^k(-1)^k$，而这个式子我们可以用二项式定理来做，我们由于 $1$ 的任何次方都是 $1$，因此我们可以将 $S(n)$ 看成 $C_k^01^k(-1)^0+C_k^11^{k-1}(-1)^1+…+C_k^k1^0(-1)^k$，可以发现这就是 $(1-1)^k$，由于 $k\geq 1$，所以 $(1-1)^k$ 必然是 $0$。由此得证。

莫比乌斯反演定理： 对于定义在正整数域上的两个函数 $F(n)$ 和 $f(n)$，若 $F(n)=\sum_{d \vert n} f(d)$，则 $f(n)=\sum_{d \vert n} \mu{(d)} F(\frac{n}{d})$

证明也比较简单，我们先将 $F(\frac{n}{d})$ 的展开，$\sum_{d \vert n} \mu{(d)} F(\frac{n}{d})=\sum_{d \vert n} \mu{(d)} \sum_{i \vert \frac{n}{d}} f(i)$。然后可以进行求和次序变换，可以发现当 $d=1$ 是 $i$ 是可以取遍 $n$ 的所有约数的，并且 $i\vert \frac{n}{d}$ 通过等价变换能得到 $d \vert \frac{n}{i}$，因此对于每个 $i$，能和他配对 $d$ 都满足 $d \vert \frac{n}{i}$，因此就可以将原式变成 $\sum_{i \vert n} f(i) \sum_{d \vert \frac{n}{i}} \mu{(d)}$。

而 $\sum_{d \vert \frac{n}{i}} \mu{(d)}$ 就是 $S(\frac{n}{i})$，而 $S(\frac{n}{i})$ 只有 $0$ 和 $1$ 两种取值，当 $\frac{n}{i}=1$ 时取 $1$，当 $\frac{n}{i}>1$ 时取 $0$，因此当 $i=n$ 时，$\frac{n}{i}=1$，当 $i < n$ 时，$\frac{n}{i}=0$，因此整个式子就应该等于 $f(n)$。

由此证明出了莫比乌斯反演定理。

莫比乌斯反演的推论： 对于定义在正整数域上的两个函数 $F(n)$ 和 $f(n)$，若 $F(n)=\sum_{n \vert d} f(d)$，则 $f(n)=\sum_{n \vert d} \mu{(\frac{d}{n})} F(d)$，也就是枚举 $d$ 的时候枚举的不是 $n$ 的约数，而是 $n$ 的倍数，这是莫比乌斯反演更常用的一个推论。

推论的证明略不同于定理，同样是展开 $F(d)$，$\sum_{n \vert d} \mu{(\frac{d}{n})} F(d)= \sum_{n \vert d} \mu{(\frac{d}{n})} \sum_{d \vert i} f(i)$，同样进行求和次序变换，当 $d=n$ 时 $i$ 会取遍 $n$ 的所有倍数，然后我们设 $\frac{d}{n}=d’$，那么 $d=d’n$，所以 $d’$ 需要满足 $d’ \vert \frac{i}{n}$，因此就能变换成 $\sum_{n\vert i} f(i) \sum_{d’\vert \frac{i}{n}} \mu(d’)$，而 $\sum_{d’\vert \frac{i}{n}} \mu(d’)$ 就是 $S(\frac{i}{n})$，到这里就跟定理的证明一样了，同理可以证明整个式子等于 $f(n)$。

由此证明出了莫比乌斯反演推论。

莫比乌斯反演的应用： 莫比乌斯反演最常用的是推论公式，一般都是先将 $F(n)$ 和 $f(n)$ 都定义出来，然后就能用 $F(n)$ 去算出 $f(n)$。