积性函数

参考资料

• 积性函数 - 维基百科
• 莫比乌斯函数 - 维基百科

引入

积性函数 是数论函数的一大类。它把整数的乘法结构与函数值挂钩——对互素的输入，函数值可乘。这一性质极大简化了求和与反演。

数论函数

定义在 正整数集 上的函数 $f:\mathbb{Z}^+\to\mathbb{C}$ 统称 数论函数（算术函数）。

积性函数

定义

$f$ 称为 积性函数，若：

$$\gcd(a,b)=1\Rightarrow f(ab)=f(a)f(b)$$

若对 所有 $a,b$ 都成立（不要求互素），称 完全积性。

推论

积性函数 $f$ 由 $f$ 在 素数幂 处的值完全决定：

$$n=p_1^{a_1}\cdots p_k^{a_k}\Rightarrow f(n)=\prod_{i=1}^{k}f(p_i^{a_i})$$

常见积性函数

函数	定义	完全积性
欧拉函数 $\varphi(n)$	与 $n$ 互素且 $\le n$ 的正整数个数	✗
因子个数 $d(n)$ 或 $\tau(n)$	$n$ 的正因子个数	✗
因子和 $\sigma(n)$	$n$ 的所有正因子之和	✗
莫比乌斯函数 $\mu(n)$	见下	✗
恒等函数 $I(n)$	$I(n)=n$	✓
单位函数 $\varepsilon(n)$	$\varepsilon(1)=1$，否则 $0$	✓
常数 1 $\mathbf{1}(n)$	恒等于 $1$	✓

因子函数公式

设 $n=p_1^{a_1}\cdots p_k^{a_k}$：

$$d(n)=\prod_{i=1}^{k}(a_i+1)$$ $$\sigma(n)=\prod_{i=1}^{k}\frac{p_i^{a_i+1}-1}{p_i-1}$$

莫比乌斯函数

定义：

$$\mu(n)=\begin{cases}1,&n=1 \\ (-1)^k,&n=p_1p_2\cdots p_k\,(\text{所有素因子互不相同}) \\ 0,&n\text{ 含平方因子}\end{cases}$$

例：$\mu(1)=1,\mu(2)=-1,\mu(4)=0,\mu(6)=1,\mu(30)=-1$。

重要恒等式

$$\sum_{d\mid n}\mu(d)=\varepsilon(n)=\begin{cases}1,&n=1 \\ 0,&n>1\end{cases}$$

这是莫比乌斯反演的核心。

狄利克雷卷积

定义：

$$(f*g)(n)=\sum_{d\mid n}f(d)\,g\!\left(\frac{n}{d}\right)$$

性质：

• 交换律、结合律 成立。
• 单位元：$\varepsilon$，即 $f*\varepsilon=f$。
• 积性函数的卷积仍是积性函数。

经典卷积关系

$$\mathbf{1}*\mu=\varepsilon$$ $$\mathbf{1}*I=\sigma\quad(\text{因子求和})$$ $$\mathbf{1}*\mathbf{1}=d\quad(\text{因子计数})$$ $$\varphi*\mathbf{1}=I\quad(\text{即 }\sum_{d\mid n}\varphi(d)=n)$$

莫比乌斯反演

设 $F(n)=\sum_{d\mid n}f(d)$，则：

$$f(n)=\sum_{d\mid n}\mu(d)\,F\!\left(\frac{n}{d}\right)$$

记号形式：$F=f*\mathbf{1}\Rightarrow f=F*\mu$。

提示

莫比乌斯反演的本质：在「整除偏序」的格上做容斥。 应用极广——计数互素对、欧拉函数求和、求 $\sum_{d\mid n}f(d)$ 的逆问题等。

应用：欧拉函数求和

由 $\varphi*\mathbf{1}=I$ 反演：

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

由此可重新推出欧拉函数的乘积公式。

线性筛求积性函数

利用欧拉筛 $O(N)$ 求一个积性函数 $f$ 在 $1\sim N$ 的值：

1. 对每个素数 $p$，已知 $f(p)$ 的公式。
2. 对每个数 $n$，记其最小素因子为 $p$：
   • 若 $p\nmid (n/p)$（即 $n/p$ 与 $p$ 互素）：$f(n)=f(p)\cdot f(n/p)$。
   • 否则：用积性函数关于 $p^k$ 的递推公式。

这一技巧广泛用于算法竞赛中的数论问题。