注意：本文运用 LATEX 较多，可能会炸，请使用 $\text{Typora v0.0.95 } 或以上级别观看。$

莫比乌斯反演

1. 莫比乌斯函数

定义 $x = {p_1}^{\alpha_1} \times {p_2}^{\alpha_2}\times {p_3}^{\alpha_3}\times \cdots {p_k}^{\alpha_k}$。

莫比乌斯函数的定义：$\mu(x) = \big\{\matrix{&0\quad \exists\ \alpha_2\ge 2\;\\&(-1)^k\quad \exists\ \alpha_i = 1}$ 。

举一个例子：$6 = 2 \times 3 \rightarrow_\ \mu(6) = 1$，$7 = 7\rightarrow_\ \mu(7) = -1$，$8 = 2^3 \rightarrow_\ \mu(8) = 0$。

一个比较有用的性质：我们定义 $\eta(i) = \sum_{\large d \mid n} \mu(i)$，那么 $\eta(i) = \big \lbrace \matrix{& 1\quad n=1\\& 0\quad n\gt 1}$ 。举个栗子：$\eta(6) = \mu(1) + \mu(2) + \mu(3) + \mu(6) = 1 + (-1) + (-1) + 1 = 0$。

性质的证明：$n\in [2, +\infin)\text{且}n\in N^+$ 的因式分解是 $n = {p_1}^{\alpha_1}\times {p_2}^{\alpha_2}\times {p_3}^{\alpha_3}\times \cdots {p_k}^{\alpha_k}$，则 $k\ge 1$ 为必然，我们对于其中的任意的一个因数 $\delta = {\wp_1}^{\ell_1}\times {\wp_2}^{\ell_2}\times {\wp_3}^{\ell_3}\times \cdots\times {\wp_\Bbbk}^{\ell_\Bbbk}$，那么 $\forall\ i\le \min(k,\: \Bbbk),\quad 0\le p_i\le \wp_i$。

然后对于 $\eta(x)$，分解质因数形式为 $n = {p_1}^{\alpha_1}\times {p_2}^{\alpha_2}\times {p_3}^{\alpha_3}\times \cdots {p_k}^{\alpha_k}$，通过性质可知若 $\exists\ 1\le i\le k, \quad \alpha_i\ge 2$，那么 $\mu(i) = 0$。所以我们不需要考虑 $a_i\ge 2$ 的情况。

然后对于上面的式子，$\mu(x)$ 就是到最后式子里面选了多少个数为 $1$，可以推出 $\eta(x)=(-1)^{\sum_{i=1}^{n} \alpha_i}$，即 $\eta (i) = \tt{\sum_{i=0}^{k} C_k^i\times (-1)^i}$。

通过二项式定理可得 $(a+b)^k = \tt{\sum_{i=0}^{k} C_{k}^{i} \times a_{k-i}\times b^k}$，这个时候我们将 $a=1$，$b=-1$ 代入前面的式子中，很明显，$(1 + (-1))^k = 0^k = 0$，那我们将这个式子用二项式定理展开，答案变成 $\tt{\sum_{i=0}^{k} C_k^0\times (-1)^i}$。所以前面的 $\eta(i)=0$。两式相等，得证。

2. 莫比乌斯反演

莫比乌斯反演定理：若 $\digamma(x) = \sum_{d\mid x} f(d)$，则 $f(x) = \sum_{d\mid x} \mu(d)\times \digamma(\frac{n}{d})$。

如果现在我们想要求 $f(x)$，但是 $f(x)$ 不好求，我们就可以运用 “正难则反” 的思想，求出 $\digamma(x)$，然后再通过 $\digamma(x)$ 来推出 $f(x)$。

上面莫比乌斯反演定理的证明：$\sum_{\\d\mid n}\mu(d)\digamma(\frac{n}{d}) = \sum_{d\mid n} (\mu(d) \sum_{i\mid \frac{n}{d}} f(i))$。

我们可以将这一个式子想象成双重循环：第一重循环循环 $n$ 的所有的约数，第二重循环循环 $\frac{n}{d}$ 的所有的约数，然后求解中间的式子。

将上面的式子化简后得到 $\sum_{\\i\mid n}\; f(i)\sum_{d\mid \frac{n}{i}} \mu(d)$ 。

然后将上面的式子代入，就得到了 $f(n)$。

3. 例题

（等待补全）

元代码

注意：本文运用 LATEX 较多，可能会炸，请使用 $\text{Typora v0.0.95 } 或以上级别观看。$

## 莫比乌斯反演

#### 1. 莫比乌斯函数

定义 $x = {p_1}^{\alpha_1} \times {p_2}^{\alpha_2}\times {p_3}^{\alpha_3}\times \cdots {p_k}^{\alpha_k}$。

莫比乌斯函数的定义：$\mu(x) = \big\{\matrix{&0\quad \exists\ \alpha_2\ge 2\;\\&(-1)^k\quad \exists\  \alpha_i = 1}$  。

举一个例子：$6 = 2 \times 3 \rightarrow_\ \mu(6) = 1$，$7 = 7\rightarrow_\ \mu(7) = -1$，$8 = 2^3 \rightarrow_\ \mu(8) = 0$。

一个比较有用的性质：我们定义 $\eta(i) = \sum_{\large d \mid n} \mu(i)$，那么 $\eta(i) = \big \lbrace \matrix{& 1\quad n=1\\& 0\quad n\gt 1}$  。举个栗子：$\eta(6) = \mu(1) + \mu(2) + \mu(3) + \mu(6) = 1 + (-1) + (-1) + 1 = 0$。

性质的证明：$n\in [2, +\infin)\text{且}n\in N^+$ 的因式分解是 $n = {p_1}^{\alpha_1}\times {p_2}^{\alpha_2}\times {p_3}^{\alpha_3}\times \cdots {p_k}^{\alpha_k}$，则 $k\ge 1$ 为必然，我们对于其中的任意的一个因数 $\delta = {\wp_1}^{\ell_1}\times {\wp_2}^{\ell_2}\times {\wp_3}^{\ell_3}\times \cdots\times {\wp_\Bbbk}^{\ell_\Bbbk}$，那么 $\forall\ i\le \min(k,\: \Bbbk),\quad 0\le p_i\le \wp_i$。

然后对于 $\eta(x)$，分解质因数形式为 $n = {p_1}^{\alpha_1}\times {p_2}^{\alpha_2}\times {p_3}^{\alpha_3}\times \cdots {p_k}^{\alpha_k}$，通过性质可知若 $\exists\ 1\le i\le k, \quad \alpha_i\ge 2$，那么 $\mu(i) = 0$。所以我们不需要考虑 $a_i\ge 2$ 的情况。

然后对于上面的式子，$\mu(x)$ 就是到最后式子里面选了多少个数为 $1$，可以推出 $\eta(x)=(-1)^{\sum_{i=1}^{n} \alpha_i}$，即 $\eta (i) = \tt{\sum_{i=0}^{k} C_k^i\times (-1)^i}$。

通过二项式定理可得 $(a+b)^k = \tt{\sum_{i=0}^{k} C_{k}^{i} \times a_{k-i}\times b^k}$，这个时候我们将 $a=1$，$b=-1$ 代入前面的式子中，很明显，$(1 + (-1))^k = 0^k = 0$，那我们将这个式子用二项式定理展开，答案变成 $\tt{\sum_{i=0}^{k} C_k^0\times (-1)^i}$。所以前面的 $\eta(i)=0$。两式相等，得证。

#### 2. 莫比乌斯反演

莫比乌斯反演定理：若 $\digamma(x) = \sum_{d\mid x} f(d)$，则 $f(x) = \sum_{d\mid x} \mu(d)\times \digamma(\frac{n}{d})$。

如果现在我们想要求 $f(x)$，但是 $f(x)$ 不好求，我们就可以运用 “正难则反” 的思想，求出 $\digamma(x)$，然后再通过 $\digamma(x)$ 来推出 $f(x)$。

上面莫比乌斯反演定理的证明：$\sum_{\\d\mid n}\mu(d)\digamma(\frac{n}{d}) = \sum_{d\mid n} (\mu(d) \sum_{i\mid \frac{n}{d}} f(i))$。

我们可以将这一个式子想象成双重循环：第一重循环循环 $n$ 的所有的约数，第二重循环循环 $\frac{n}{d}$ 的所有的约数，然后求解中间的式子。

将上面的式子化简后得到 $\sum_{\\i\mid n}\; f(i)\sum_{d\mid \frac{n}{i}} \mu(d)$ 。

然后将上面的式子代入，就得到了 $f(n)$。

#### 3. 例题

（等待补全）