积性函数

参考资料

• 积性函数 - 维基百科
• 莫比乌斯函数 - 维基百科
• 狄利克雷卷积 - 维基百科
• 积性函数 - OI Wiki

引入

积性函数（Multiplicative Function）是数论函数里最重要的一大类。它的核心特征是：把整数的乘法结构和函数值挂上钩——只要两个输入互素，函数值就可以相乘。

这一条性质看似简单，威力却很大。借助 算术基本定理，任何整数都是素数幂的乘积；而积性函数在互素的块上可乘，于是它在任意整数处的值，都能从「素数幂处的值」拼出来。这意味着研究一个积性函数，只需要搞清楚它在 $p^k$ 上长什么样，整体就全清楚了。它让大量带 $\sum_{d\mid n}$ 的求和与反演问题瞬间简化。

数论函数

定义在 正整数集 上的函数 $f:\mathbb{Z}^+\to\mathbb{C}$ 统称 数论函数（Arithmetic Function，算术函数）。它的输入是正整数，输出可以是任意（通常是整数或复数）。本节研究的都是其中结构特别好的那些。

积性函数

定义

数论函数 $f$（且 $f$ 不恒为 $0$）称为 积性函数，若对所有互素的 $a,b$ 都有：

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

若把条件放宽到对 所有 $a,b$（不要求互素）都成立，则称 完全积性函数（Completely Multiplicative）。任何积性函数都满足 $f(1)=1$（取 $a=b=1$ 即得）。

推论

把唯一分解代入定义，积性函数 $f$ 的值由它在 各素数幂处的值 完全决定：

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

这就是上面说的「只需搞清 $p^k$」。对完全积性函数还更简单：$f(p^k)=f(p)^k$，连素数幂都不用单独算，知道 $f$ 在素数上的值就够了。

常见积性函数

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

tip

后三个看似平凡的函数（$\operatorname{id}$、$\varepsilon$、$\mathbf{1}$）不是凑数的——它们是下面狄利克雷卷积里的「基本元件」。$\varepsilon$ 是卷积的单位元（相当于乘法里的 $1$），$\mathbf{1}$ 负责「对所有因子求和」，$\operatorname{id}$ 负责把因子本身取出来。许多经典恒等式都是这几个零件的卷积。

欧拉函数

欧拉函数 $\varphi(n)$ 数的是 $\set{1,\dots,n}$ 中与 $n$ 互素的个数。由唯一分解和积性可得：

$$\varphi(n)=\prod_{i=1}^{k}\left(p_i^{a_i}-p_i^{a_i-1}\right)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right)$$

它满足 $\varphi(p)=p-1$、$\varphi(p^k)=p^k-p^{k-1}$，是积性但 非 完全积性（例如 $\varphi(4)=2\ne\varphi(2)^2=1$）。

例：算 $\varphi(360)$。分解 $360=2^3\cdot 3^2\cdot 5$，用乘积公式：

$$\varphi(360)=360\left(1-\frac12\right)\left(1-\frac13\right)\left(1-\frac15\right)=360\cdot\frac12\cdot\frac23\cdot\frac45=96$$

也可逐素数幂相乘：$\varphi(2^3)\varphi(3^2)\varphi(5)=(8-4)(9-3)(5-1)=4\times 6\times 4=96$，两法一致。所以 $1\sim 360$ 中与 $360$ 互素的数有 $96$ 个。

因子函数

设 $n=p_1^{a_1}\cdots p_k^{a_k}$。因子个数 $d(n)$ 与 因子和 $\sigma(n)$ 都能直接从分解读出：

$$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}$$

$d(n)$ 的来历：$n$ 的每个因子，在素数 $p_i$ 上的指数可以是 $0,1,\dots,a_i$ 共 $a_i+1$ 种选择，各素数独立，乘起来即得。$\sigma(n)$ 同理，把每个 $p_i$ 上的等比和 $1+p_i+\dots+p_i^{a_i}$ 乘起来。

例：算 $n=72=2^3\cdot 3^2$ 的 $d$ 与 $\sigma$。

$$d(72)=(3+1)(2+1)=12,\qquad \sigma(72)=(1+2+4+8)(1+3+9)=15\times 13=195$$

可把 $72$ 的 $12$ 个因子全列出来核对：$1,2,3,4,6,8,9,12,18,24,36,72$，正好 $12$ 个，相加得 $195$。手工列因子时按「每个素数取一档指数」的笛卡儿积来枚举（$2$ 的指数 $\times$ $3$ 的指数），不易漏。

莫比乌斯函数

莫比乌斯函数（Möbius Function）$\mu(n)$ 定义为：

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

它把整数分三类：$1$、无平方因子数（按素因子个数定正负号）、有平方因子数（直接归零）。例如 $\mu(1)=1,\ \mu(2)=-1,\ \mu(4)=0,\ \mu(6)=1,\ \mu(30)=-1$。$\mu$ 是积性函数。

核心恒等式

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

这条恒等式是整个莫比乌斯反演的心脏。它本质上是一个容斥：对 $n>1$，把 $n$ 的无平方因子的因子按素因子个数分类，正负正好抵消（二项式系数交错和为 $0$）。它说的是「$\mathbf{1}*\mu=\varepsilon$」，即 $\mu$ 是 $\mathbf{1}$ 在卷积下的逆。

例：在 $n=30=2\cdot 3\cdot 5$ 上验证。$30$ 的因子按素因子个数分层：$1$（$0$ 个，$\mu=1$）；$2,3,5$（$1$ 个，$\mu=-1$）；$6,10,15$（$2$ 个，$\mu=1$）；$30$（$3$ 个，$\mu=-1$）：

$$\sum_{d\mid 30}\mu(d)=\underbrace{1}_{1}-\underbrace{3}_{2,3,5}+\underbrace{3}_{6,10,15}-\underbrace{1}_{30}=0$$

这串 $1-3+3-1$ 正是 $(1-1)^3$ 的二项展开——$k$ 个不同素因子时和为 $(1-1)^k=0$，所以 $n>1$ 时必为 $0$。

狄利克雷卷积

两个数论函数 $f,g$ 的 狄利克雷卷积（Dirichlet Convolution）定义为：

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

即对 $n$ 的每一种「因子配对」$d\cdot\frac nd=n$ 求和。它把「数论函数」从一盘散沙变成一个 有乘法的代数系统：

例：直接按定义算 $(\mathbf{1}*\operatorname{id})(12)$，体会卷积是「遍历因子配对求和」。$12$ 的因子为 $1,2,3,4,6,12$，每项取 $\mathbf{1}(d)\cdot\operatorname{id}(12/d)=1\cdot\frac{12}{d}$：

$$(\mathbf{1}*\operatorname{id})(12)=\sum_{d\mid 12}\frac{12}{d}=12+6+4+3+2+1=28=\sigma(12)$$

正是 $12$ 的因子和，印证下面 $\mathbf{1}*\operatorname{id}=\sigma$。同样地 $(\mathbf{1}*\mathbf{1})(12)=\sum_{d\mid 12}1=6=d(12)$（$12$ 有 $6$ 个因子），印证 $\mathbf{1}*\mathbf{1}=d$。

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

正因为有了结合律和单位元，「求某个函数的逆」「在等式两边同卷一个函数」这类操作才合法——莫比乌斯反演就是这么来的。

经典卷积关系

下面几条等式把上面所有函数串了起来，值得记熟：

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

最后一条尤其漂亮，下面单独说。

经典恒等式

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

直觉上，把 $\set{1,2,\dots,n}$ 每个数 $\frac kn$ 约分成最简分数，分母一定是 $n$ 的某个因子 $d$；分母恰为 $d$ 的最简分数有 $\varphi(d)$ 个。按分母分类求和，总数仍是 $n$，于是各 $\varphi(d)$ 加起来等于 $n$。

例：在 $n=12$ 上验证。$12$ 的因子 $1,2,3,4,6,12$，对应

$$\sum_{d\mid 12}\varphi(d)=\varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)+\varphi(6)+\varphi(12)=1+1+2+2+2+4=12$$

正好等于 $n=12$。换个角度看分母分类：把 $\frac{1}{12},\frac{2}{12},\dots,\frac{12}{12}$ 全约分，分母为 $12$ 的最简分数（即分子与 $12$ 互素）有 $\varphi(12)=4$ 个，分母为 $6$ 的有 $\varphi(6)=2$ 个……各档加起来仍是 $12$ 个分数。

另一条常用的是因子和与莫比乌斯的互逆形式（莫比乌斯反演的特例）：

$$\sum_{d\mid n}\mu(d)\,\sigma\!\left(\frac nd\right)=\operatorname{id}(n)=n$$

莫比乌斯反演

莫比乌斯反演（Möbius Inversion）：设 $F(n)=\sum_{d\mid n}f(d)$，则可以把 $f$ 反解出来：

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

用卷积语言写极其干净：$F=f*\mathbf{1}\Rightarrow f=F*\mu$。证明只需在两边同卷 $\mu$，再用 $\mathbf{1}*\mu=\varepsilon$ 化简。

tip

莫比乌斯反演的本质是「在整除偏序的格上做容斥」。如果你知道的是「所有因子的累加 $F$」，却想倒推出「单点的原值 $f$」，$\mu$ 就是那把把累加「拆回去」的钥匙——正号、负号、归零，正对应容斥里的加、减、不计。它在计数互素对、求 $\gcd$ 相关求和、欧拉函数求和等问题里出现得极频繁。

应用：重推欧拉函数公式

由 $\varphi*\mathbf{1}=\operatorname{id}$ 两边同卷 $\mu$，得 $\varphi=\operatorname{id}*\mu$，即：

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

把右边对每个素因子展开（含平方因子的项被 $\mu$ 清零），正好得到 $n\prod_{p\mid n}\bigl(1-\frac1p\bigr)$，与前面的乘积公式吻合。这是「反演能重新推出已知结果」的典型例子。

例：在 $n=12$ 上把 $\varphi=\operatorname{id}*\mu$ 算一遍，看含平方因子项如何被清零。$12$ 的因子里 $\mu$ 非零的只有无平方因子的 $1,2,3,6$（$4,12$ 含 $2^2$，$\mu=0$）：

$$\varphi(12)=\sum_{d\mid 12}\mu(d)\frac{12}{d}=\mu(1)\cdot 12+\mu(2)\cdot 6+\mu(3)\cdot 4+\mu(6)\cdot 2=12-6-4+2=4$$

（$\mu(1)=1,\mu(2)=\mu(3)=-1,\mu(6)=1$。）结果 $\varphi(12)=4$ 与直接公式一致，而 $d=4,12$ 那两项因 $\mu=0$ 自动消失。

例（反解未知函数）：已知 $g(n)=\sum_{d\mid n}f(d)$，且测得 $g(1)=1,\ g(2)=3,\ g(3)=4,\ g(6)=12$，反求 $f(6)$。直接套 $f(n)=\sum_{d\mid n}\mu(d)\,g(n/d)$：

$$f(6)=\mu(1)g(6)+\mu(2)g(3)+\mu(3)g(2)+\mu(6)g(1)=12-4-3+1=6$$

这正是「已知所有因子处的累加值、倒推单点原值」的标准反演操作——符号 $+,-,-,+$ 恰是容斥的加减。

线性筛求积性函数

利用 线性筛（欧拉筛）可在 $O(N)$ 时间内求出一个积性函数 $f$ 在 $1\sim N$ 的全部取值。关键是筛法保证每个合数只被它的 最小素因子 $p$ 划掉一次，于是分两种情况递推：

1. 对每个素数 $p$，按 $f(p)$ 的已知公式直接赋值。
2. 对合数 $n$（设最小素因子为 $p$）：
   • 若 $p\nmid(n/p)$，即 $n/p$ 与 $p$ 互素：用积性 $f(n)=f(p)\cdot f(n/p)$。
   • 否则 $p^2\mid n$：用 $f$ 在 $p^k$ 上的递推式（如 $\varphi(p^k)=p\cdot\varphi(p^{k-1})$）。

这一技巧在算法竞赛的数论题里几乎是标配，常与莫比乌斯反演配合，把整除求和问题压到线性甚至更优。

例：跟着线性筛求 $\varphi(1)\sim\varphi(12)$，看三种赋值分支如何触发。$\varphi(1)=1$。逐个处理：

• $\varphi(2)=1,\varphi(3)=2,\varphi(5)=4,\varphi(7)=6,\varphi(11)=10$：素数，$\varphi(p)=p-1$。
• $\varphi(4)$：$4=2\times 2$，最小素因子 $p=2$ 且 $p\mid(4/2)=2$，落到 $p^2\mid n$ 分支，$\varphi(4)=p\cdot\varphi(2)=2\times 1=2$。
• $\varphi(6)$：$6=2\times 3$，$p=2$ 但 $p\nmid(6/2)=3$（互素），用积性 $\varphi(6)=\varphi(2)\varphi(3)=1\times 2=2$。
• $\varphi(8)$：$8=2\times 4$，$p=2\mid 4$，$\varphi(8)=2\times\varphi(4)=2\times 2=4$。
• $\varphi(9)$：$9=3\times 3$，$p=3\mid 3$，$\varphi(9)=3\times\varphi(3)=3\times 2=6$。
• $\varphi(10)$：$10=2\times 5$，$p=2\nmid 5$，$\varphi(10)=\varphi(2)\varphi(5)=1\times 4=4$。
• $\varphi(12)$：$12=2\times 6$，$p=2\mid 6$，$\varphi(12)=2\times\varphi(6)=2\times 2=4$。

关键在于「$p\mid(n/p)$ 与否」决定走 素数幂递推 还是 积性拆分——前者乘的是 $p$，后者乘的是 $\varphi(p)=p-1$。差一个 $1$，必须分清。

完全数与梅森素数

因子和 $\sigma$ 引出一个古老话题。若一个正整数恰好等于它 所有真因子之和，即 $\sigma(n)=2n$，称为 完全数（Perfect Number）。最小的几个是 $6=1+2+3$、$28=1+2+4+7+14$。

偶完全数有一条优美刻画（欧几里得—欧拉定理）：$n$ 是偶完全数当且仅当

$$n=2^{p-1}\bigl(2^p-1\bigr),\quad\text{其中 }2^p-1\text{ 是素数}$$

形如 $2^p-1$ 的素数称为 梅森素数（Mersenne Prime），$p$ 本身必为素数。于是「找偶完全数」与「找梅森素数」是同一个问题。梅森素数极其稀少，目前已知的只有几十个，最大素数纪录长期由它保持。至于 是否存在奇完全数，至今仍是未解之谜。

例：用欧几里得—欧拉公式造出前几个完全数。逐个试素数 $p$，看 $2^p-1$ 是否为素数：

$p$	$2^p-1$	是否素数	完全数 $2^{p-1}(2^p-1)$
$2$	$3$	✓	$2\times 3=6$
$3$	$7$	✓	$4\times 7=28$
$5$	$31$	✓	$16\times 31=496$
$7$	$127$	✓	$64\times 127=8128$
$11$	$2047=23\times 89$	✗（非素数）	—

注意 $p=11$ 虽是素数，$2^{11}-1=2047$ 却是合数，故不产生完全数——「$p$ 素」是必要而非充分条件。验算 $\sigma(28)$：$28=2^2\cdot 7$，$\sigma(28)=(1+2+4)(1+7)=7\times 8=56=2\times 28$，确为完全数。