莫比乌斯反演

数论函数的积性

若 $f(x)$ 满足 $\forall x_1,x_2,(x_1,x_2)=1$ 都有 $f(x_1\times x_2)=f(x_1)\times f(x_2)$ 那么称f(x)为积性函数
Eg.

• $\varphi(n)$ 表示小于n且与n互质的数的个数
• $\mu(n)$ 莫比乌斯函数.
  设 $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_t^{\alpha_t}$
  若 $\exists \alpha_k>1$ 则 $\mu(n)=0$
  否则 $\mu(n)=(-1)^t$
• $\sigma(n)$ 表示n的约数和
• $id(n)=n$
• $1(n)=1$
• $\varepsilon(n)$
  若 $n=1$ 时 $\varepsilon(n)=1$
  否则 $\varepsilon(n)=0$

迪利克雷卷积

定义 $h=fg$ , 其中``运算为迪利克雷卷积。
则

$$h(d)=\sum _{t\mid d} f(t)\times g(\frac{d}{t})$$

特别注意，若 $f$ , $g$ 均为积性函数，那么 $h$ 也为积性函数。

---

证明如下:

$$\begin{aligned} h(d)&=\sum _{t\mid d} f(t)\times g(\frac{d}{t})\\ h(d_1d_2) &= \sum _{t\mid d_1d_2} f(t)\times g(\frac{d_1d_2}{t})\\ &=\sum _{t_1\mid d_1,t_2\mid d_2} f(t_1t_2)\times g(\frac{d_1d_2}{t_1t_2})\\ &=\sum _{t_1\mid d_1,t_2\mid d_2} f(t_2)\times g(\frac{d_1}{t_1})g(\frac{d_2}{t_2})\\ &=\sum _{t_1\mid d_1}\sum_{t_2\mid d_2}f(t_1)\times g(\frac{d_1}{t_1}) \times f(t_2)\times g(\frac{d_2}{t_2})\\ &=\sum _{t_1\mid d_1}f(t_1)\times g(\frac{d_1}{t_1})\sum_{t_2\mid d_2} f(t_2)\times g(\frac{d_2}{t_2})\\ &=h(d_1)h(d_2) \end{aligned}$$

迪利克雷卷积的性质

$$\varphi * 1 = id$$ $$\mu * id = \varphi$$ $$\mu * 1 =\varepsilon$$ $$id *1 = \sigma$$

证明其一

$$\varphi * 1 = id$$

证明如下:

$$\begin{aligned} h(d)&=\sum _{t\mid d}\varphi(t)=d\\ &=\sum_{t\mid d}t\prod(1-\frac{1}{p_i})\\ &=\sum_{t\mid d}\prod p_i^k(1-\frac{1}{p_i})\\ d&=\prod p_i^{\alpha_{i}}\\ 现在类似&考虑d的因数，若有因子p_i\\ 那提出因式&\ \ \ \ \ (p_i+p_i^{2}+p_i^3+\cdots +p_i^{\alpha_{i}})\\ &=p_i\times\frac{p_i^{\alpha_{i}}-1}{p_i-1}\\ h(d)中有&\prod(1-\frac{1}{p_i})=\prod(\frac{p_i-1}{p_i})\\ \end{aligned}$$

综合起来,不难发现h(d)可以通过枚举因数来求
枚举因数 $a_1-a_k$