积性函数的定义

对于一个函数 $f(x)​$，有互质的两数 $a,b​$，如果函数具有 $f(a b) = f(a) f(b)​$的性质，那么此类型的函数被称为积性函数。

完全积性函数：若一个积性函数 $f(x)$，具有 $f(x ^ k) = f^k(x)$，那么此函数成为完全积性函数。

常见的积性函数

1.$\varphi (x)$：欧拉函数，表示小于 $x$ 且与 $x$ 互质的数的个数。

2.$\mu (x)$：莫比乌斯函数，关于非平方数的质因子数目的函数。

莫比乌斯函数这样计算：

$$\mu(x) = \begin{cases} 1 \ \ \ \ \ \ \ \ \ \ (x = 1) \\\\ (-1) ^ k \ \ (x = p_1p_2p_3...p_k) \\\\ 0 \ \ \ \ \ \ \ \ \ \ \texttt{其他情况}\end{cases}$$

3.$d(x)​$：约数个数函数，表示 $x​$ 的约数个数。

4.$\sigma(x)​$：约数和函数，表示 $x​$ 的各约数之和。

5.$I(x)​$：不变函数，此函数的值恒为1，此函数是完全积性函数

6.$\epsilon(x)$：元函数，此函数的计算方式为：若 $x = 1$，$\epsilon(x) = 1$，若 $x > 1$，$\epsilon(x) = 0$，此函数为完全积性函数。

7.$id(x)$：单位函数，计算方式为 $id(x) = x$ ，此函数为完全积性函数。

8.$idk(x)$：幂函数，计算方式为 $idk(x) = x ^ k$，此函数为完全积性函数。

9.$\lambda(x)$：刘维尔函数，计算方式：设 $\Omega(x)$ 为 $x$ 的质因子的数目，则 $\lambda(x) = (-1) ^ {\Omega(x)}$

一些积性函数常用的性质

1.

$$\sum_{d | n} \mu(d) = \begin{cases} 1 (n = 1) \\\\ 0 (n > 1) \end{cases}​$$

2.

$$\sum_{d^2 | n} \mu(\frac{n}{d^2}) = \lambda(n)​$$

3.

$$\sum_{d | n}\frac{\mu(d)}{d} = \frac{\varphi(n)}{n}$$

4.

$$\sum_{d | n} \varphi(n) = n$$

5.

对于任意积性函数 $f(x)$，都有 $f*\epsilon=f$

一些常用的卷积

1.$I * \varphi = id$

2.$\mu * I = \epsilon$

3.$id * \mu = \varphi$

4.$\mu * d = I$

5.$id * \mu = \varphi * \epsilon$