积性函数与狄利克雷卷积

积性函数

定义

积性函数是指一个定义域为正整数 $N$ 的算术函数 $f(n)$ ，有如下性质：$f(1) = 1$ ，且 $\forall a,b \in \mathbb{N}^{+} \quad $ 且 $\quad \gcd(a,b) = 1$ ，有 $f(ab) = f(a) f(b)$。

若对于任意的 $a,b$ ， $f$ 均满足上述性质，则称此函数为完全积性函数。

积性函数举例：

$\varphi (n)$－欧拉$\varphi$函数，计算与$n$ 互质的正整数之数目
$\mu (n)$－默比乌斯函数，关于非平方数的质因子数目
$\gcd(n,k)$ －最大公因数，当 $k$ 固定的情况
$\sigma _{k}(n)$ - 除数函数，$n$ 的所有正因数的 $k$ 次幂之和，当中 $k$ 可为任何复数。在特例中有：

$\sigma_0(n) = d(n)$ - $n$ 的正因数数目

$\sigma _{1}(n) = \sigma (n)$ - $n$ 的所有正因数之和
$I(n)$ －不变的函数，定义为 $I(n) = 1$ （完全积性）
$Id(n)$ －单位函数，定义为 $Id(n) = n$ （完全积性）
$Id_k(n)$ －幂函数，对于任何复数、实数 $k$，定义为 $Id_k(n) = n^k$ （完全积性）
$\varepsilon(n)$ －定义为：若 $n = 1，\varepsilon(n) = 1$；若 $n > 1，\varepsilon(n) = 0$ 。有时称为“对于狄利克雷卷积的乘法单位”（完全积性）
$(n/p)$ －勒让德符号，$p$ 是固定质数（完全积性）
$\lambda(n)$ －刘维尔函数，关于能整除 $n$ 的质因子的数目
$\gamma(n)$ - 定义为 $\gamma(n) = (-1) ^ {\omega(n)}$，在此加性函数 $\omega(n)$ 是不同能整除n的质数的数目

性质

积性函数的值完全由质数的幂决定，这和算术基本定理有关。

即是说，若将 $n$ 表示成质因数分解式如 ${p_{1}}^{a_{1}}{p_{2}}^{a_{2}} \cdots {p_{k}}^{a_{k}}$，则 $f(n) = f({p_{1}}^{a_{1}})f({p_{2}}^{a_{2}}) \cdots f({p_{k}}^{a_{k}}) $。

若f为积性函数且 $f(p^{n}) = f(p)^{n}$，则 $f$ 为完全积性函数。

那么，这玩意跟狄利克雷卷积有什么关系呢？

这里有一条：两个积性函数的狄利克雷卷积必定是积性函数。因此，以卷积为群的运算，所有积性函数组成了一个子群。

常见积性函数筛法

注意到积性函数有一条十分重要的性质：任意积性函数都可以用线性筛 $O(n)$ 求得 。

不知道线性筛的，请出门右转。

Möbius 函数

定义

莫比乌斯函数（$M\ddot{o}bius$ 函数） $\mu$ 是指以下的函数：

设正整数 $N$ 按照算数基本定理分解质因数为 $N = {p_{1}}^{a_{1}}{p_{2}}^{a_{2}} \cdots {p_{m}}^{a_{m}}$ ，定义函数：

$$\mu(N) = \begin{cases}0 & \exists i \in \left[1,m \right] \ ,c_i > 1 \\ 1 & m\equiv 0\pmod{2} \ ,\forall i \in \left[1,m\right] \ ,c_i = 1 \\ -1 & m\equiv 1\pmod{2} \ ,\forall i \in \left[1,m\right] \ ,c_i = 1\end{cases}$$

注：若 $\mu(a) = 0$ ，则 $a$ 是某个完全平方数的整数倍。

$M\ddot{o}bius$ 函数也可表示为以下形式：

$$\mu(N) = \delta^{\Omega(N)}_{\omega(N)} \lambda(N)$$

其中 $\delta$ 是 $Kronecker$ 符号， $\lambda(N)$ 是刘维尔函数， $\omega(N)$ 是不同的素因子的数量 $Ñ$ ，和 $\Omega(N)$ 是素因子数 $Ñ$，具有多重性计数。（摘自百度）

看不懂是不是，~~我也看不懂~~，$\cdots$ 有兴趣的读者可以自己上百度了解了解。

函数的前 $50$ 个值如下：

性质

$M\ddot{o}bius$ 函数是积性的（即，只要 $\gcd(a,b) = 1$，$\mu(ab) = \mu(a) \mu(b)$）
$\sum_{d \mid N}\mu(d) = \begin{cases}1 & n = 1\\ 0 & n \ne 1\end{cases}$

上述等式可推出重要的莫比乌斯反演公式，并且是 $\mu$ 在乘法和算术函数理论中具有相关性的主要原因。

$\mu(n)$ 在组合学中的其他应用与组合群和组合枚举中 $Pólya$ 枚举定理的使用有关。（摘自百度，这些内容当然现在不会写，以后有空再写）