数论函数基础

数论函数是数论中相当重要的一环，我们先来将*一些基本的函数 —— $\color {black} \textsf {H} \color {red} \textsf {\_W\_Y}$

* : 同 “讲”，讲述

全文 绝大多数 内容是对 [0] 中讲述的 粗略抄写 和 胡乱加工

关于 加性函数 和 积性函数 的部分，参考 [3]

1. 一些定义与性质

分类

数论函数

定义域 为 （全体）正整数 的函数，因其在 所有正整数 处均有定义，故可以视作数列

一般 $OI$ 中的 数论函数 的陪域* 为整数

* : 指 可能的取值范围，并不代表 实际上函数的取值范围（值域）

但显然，一个函数的值域被其陪域包含 [1]
加性函数

若 $\forall a, b \in N ^ *, a \perp b$，有 $f (ab) = f (a) + f (b)$，则称 $f$ 为 加性函数，如 本质不同质因数个数

性质式

\[\begin {aligned} f \left ( \prod p_i ^ {c_i} \right ) &= \sum f (p_i ^ {c_i}) \end {aligned} \]
判定时，先证明 $f (1) = 0$，然后 根据定义判定

此处指（数论）加性函数 $Additive ~ Function$（下文 加性函数 默认指代对象）

应当与（代数）加性函数 $Additive ~ Map$ 区分 [4]

容易发现，由于 $f (1 \times 1) = f (1) + f (1)$，有 $f (1) = 0$，为 数论加性函数 的 必要条件

后者满足 柯西方程 [2]，即 $f (x + y) = f(x) + f (y)$，且 定义域 为 有理数
完全加性函数

若 $\forall a, b \in N ^ *$，有 $f (ab) = f (a) + f (b)$，则称 $f$ 为 完全加性函数，如 总质因数个数

性质式

\[\begin {aligned} f \left ( \prod p_i ^ {c_i} \right ) &= \sum f (p_i ^ {c_i}) = \sum (c_i \cdot f (p_i)) \end {aligned} \]
判定时，先证明 $f (1) = 0$，然后证明 $\forall p' \in \mathbb P$，有 $f (p') + f (a) = f (ap')$ 即可

无需单独证明其为 加性函数

容易发现，任意 $b$ 均可以 质因数分解 成质数，故也无须证明 $f (a) + f (b) = f (ab)$
积性函数

若 $\forall a, b \in N ^ *, a \perp b$，有 $f (ab) = f (a) f (b)$，则称 $f$ 为 积性函数，如 欧拉函数 $\varphi$

性质式

\[\begin {aligned} f \left ( \prod p_i ^ {c_i} \right ) &= \prod f (p_i ^ {c_i}) \end {aligned} \]
若一个函数是 积性函数，则其 求和函数 也是 积性函数（如 因数个数 / 因数和 函数）

判定时，先证明 $f (1) = 1$，然后 根据定义判定

容易发现，$f (1) = 1$ 是 积性函数 的 必要条件

同时，我们一般不将 常值为 $0$ 的函数 视作积性函数
完全积性函数

若 $\forall a, b \in N ^ *$，有 $f (ab) = f (a) + f (b)$，则称 $f$ 为 完全积性函数，如 幂函数 $Id_k$

性质式

\[\begin {aligned} f \left ( \prod p_i ^ {c_i} \right ) &= \prod f (p_i ^ {c_i}) = \prod f (p_i) ^ {c_i} \end {aligned} \]
判定时，先证明 $f(1) = 1$，然后证明 $\forall p' \in \mathbb P$，有 $f (p')f(a) = f(ap')$ 即可

加性函数 和 积性函数 的转化

若 $f$ 为 加性函数，而函数 $g$ 满足 $g (x) = C ^ {f (x)}$，其中 $C$ 为常数

容易发现 $g (1) = C ^ {f (1)} = C ^ 0 = 1$

又 $a \perp b$ 时，$g (a) g (b) = C ^ {f (a)} \times C ^ {f (b)} = C ^ {f (a) + f (b)} = C ^ {f (ab)} = g (ab)$

故 $g$ 为 积性函数，同理，当 $f$ 为 完全加性函数 时，$g$ 为 完全积性函数

运算

数论函数的加法

对于 数论函数 $f, g$，$f + g$ 是 $f, g$ 各个位置相加 的表示，$ (f + g) (x) = f (x) + g (x)$
数论函数的数乘

对于 数 $c$ 与 数论函数 $f$，$c \cdot f$ 表示 $f$ 的 各个位置 乘 $c$，也作 $cf$，有 $(c\cdot f)(x) = c \cdot f (x)$
数论函数的点乘

对于 数论函数 $f, g$，$f \cdot g$ 是 $f, g$ 各个位置相乘 的表示，$(f \cdot g) (x) = f (x) g (x)$

为与 狄利克雷卷积 符号 $*$ 区分，点乘符号 通常 不省略

2. 常见函数，分类及证明

单位函数*：$\epsilon (n) = [n = 1]$

判断 $n$ 是否为 $1$，又被称为 元函数，完全积性函数

证明显然
常数函数*：$I(n) = 1$

无论 $n$ 取值，函数恒为 $1$，完全积性函数

证明显然
幂函数，恒等函数*：$\operatorname {id}_k (n) = n ^ k$

当 $k = 1$ 时，也记作 $\operatorname {id} (n)$，完全积性函数

证明显然

* : 注意，许多博客中称 $I(n)$ 为 恒等函数，而称 $\operatorname {id} (n)$ 为 单位函数

但与 $Wiki$ 等百科定义不符，故此处 不采用这种用法
除数函数：$\sigma_k (n) = \sum _ {d \mid n} d ^ k$

$\sigma_0 (n)$ 表示 $n$ 的 约数个数，又记作 $\tau (n)$ 或 $d (n)$，$\sigma_1 (n)$ 表示 $n$ 的 约数和，又记作 $\sigma (n)$

有计算式

\[\begin {aligned} \sigma_k (n) = \begin {cases} \prod (c_i + 1) & k = 0 \\ \prod { \frac {p_i ^ {(c_i + 1)k} - 1} {p_i - 1} } & k > 0 \end {cases} \end {aligned} \]

根据乘法分配律，有 $\sigma _ k (n) = \prod \sum _ {j = 0} ^ {c_i} p_i ^ {jk}$，等比数列求和 即可得到上式

积性函数

证明

显然有 $\sigma_k (1) = 1 ^ k = 1$，当 $a \perp b$ 时

\[\begin {aligned} \sigma _k (a) \sigma _k (b) &= \sum \limits _ {d_1 \mid a} d_1 ^ k \sum \limits _ {d_2 \mid b} d_2 ^ k \\ &= \sum \limits _ {d_1 \mid a} \sum \limits _ {d_2 \mid b} d_1 ^ k d_2 ^ k \\ &= \sum \limits _ {d_1 \mid a} \sum \limits _ {d_2 \mid b} (d_1 d_2) ^ k \\ &= \sum \limits _ {d \mid ab} d ^ k \\ &= \sigma _k (ab) \end {aligned} \]
下指标 由 $d_1 \mid a, d_2 \mid b$ 到 $d \mid ab$ 的这一步显然只有 $a \perp b$ 时满足

可以将其 唯一分解 后证明
欧拉函数：$\varphi (n) = \sum \limits _ {i = 1} ^ n [i \perp n]$

即 $n$ 以内与 $n$ 互质的数 的个数，积性函数

证明

显然有 $\varphi (1) = 1$，我们知道，当 $a \perp k, b \perp k$ 时，一定有 $ab \perp k$

由于 $a \perp b$，我们认为 $ib + k ~ (i \in [0, a - 1])$ 将构成 $a$ 的 完全剩余系

即 $ib + k$ 模 $a$ 后能得到 $a$ 的 每一种余数，反证法容易得到，前文中也有提及

故我们构建一个 $a \times b$ 的矩阵

\[\begin {array} {ccccc} 1 & 2 & 3 & \cdots & b \\ b + 1 & b + 2 & b + 3 & \cdots & 2b \\ 2b + 1 & 2b + 2 & 2b + 3 & \cdots & 3b \\ &&\cdots&& \\ (a - 1)b + 1 & (a - 1)b + 2 & (a - 1)b + 3 & \cdots & ab \end {array} \]
显然我们可以找到 $\varphi (b)$ 列与 $b$ 互质的数

（$r \perp b$ 则 $kb + r \perp b$，故只需第一行的数与 $b$ 互质，则后面对应列的数一定与 $b$ 互质）

同时 每一列都是 $n$ 的完全剩余系，故 每一列有 $\varphi (a)$ 个与 $a$ 互质的数

于是有 $\varphi (a) \varphi (b)$ 个数与 $a, b$ 均互质，则有 $\varphi (a) \varphi (b)$ 个数与 $ab$ 互质

故有 $\varphi (a) \varphi (b) = \varphi (ab)$，即 积性函数 性质得证

我们也可以通过容斥得到 $\varphi (n)$ 的 计算式

\[\varphi (n) = n \prod (1 - \dfrac 1 {p_i}) \]

可以感性理解成 对于 $n$ 的每个质因子 $p_i$，$1 \sim n$ 中有 $n (1 - \dfrac 1 {p_i})$ 个数 不被其整除

即这些数与 $n$ 没有 $p_i$ 这个公因数，对于剩下的数，继续考虑其被 $p_{i + 1}$ 整除的可能

从而

\[\begin {aligned} \varphi (n) \varphi (m) &= n \prod (1 - \dfrac 1 {p_i}) \times m \prod (1 - \dfrac 1 {p_j}) \\ &= nm \prod (1 - \dfrac 1 {p'_i}) \\ &= \varphi (nm) \end {aligned} \]
本质不同质因子个数：$\omega (n) = \sum _ {p \in \mathbb P} [p \mid n]$

加性函数

证明

显然 $\omega (1) = \sum _ {p \in \mathbb P} [p \mid 1] = 0$

\[\begin {aligned} a = \prod _ {i = 1} ^ {n} p_i , b = \prod _ {i = 1} ^ {m} q_i \end {aligned} \]
若 $\forall p_i ~ (p_i \in \mathbb P, p_i \mid a), p_i \in P$，同理 $q_i \in Q$

由于 $a \perp b$，则 $P \cap Q = \varnothing$，故 $|P| + |Q| = |P + Q|$

显然，$ab$ 分解后的 质因数集合 即为 $P + Q$，而 集合大小 就是 $\omega$ 的值

故有 $\omega (a) + \omega (b) = \omega (ab)$ 得证
莫比乌斯函数：$\mu (n)$

\[\begin {aligned} \mu (n) = \begin {cases} 1 & n = 1 \\ 0 & \exist d > 1, d ^ 2 \mid n \\ (-1) ^ {\omega (n)} & \operatorname {otherwise} \end {cases} \end {aligned} \]
$\sum _ {d \mid n} \mu (d) = [n = 1]$ [5]

显然，$n = 1$ 时，$\sum _ {d \mid n} \mu (d) = 1$，否则设 $n = \prod _ {i = 1} ^ {m} p_i ^ {c_i}$，$d = \prod _ {i = 1} ^ m p_i ^ {x_i}$

由定义，我们知道当 $d$ 有 平方因子 时，$\mu (d) = 0$，即 不做贡献

故我们只需要考虑 $x_i \in \{0, 1\}$ 的 $2 ^ m$ 种情况，设 $d$ 存在 $r$ 个 $x_i$ 为 $1$，则

\[\begin {aligned} \sum _{d \mid n} \mu (d) &= \sum _ {r = 0} ^ m {m \choose r} (-1) ^ r & (n \neq 1) \end {aligned} \]
注意到 二项式定理

\[(x + y) ^ n = \sum _ {k= 0} ^ n {n \choose k} x ^ {n - k} y ^ k \]
容易发现，当 $n = m, x = 1, y = -1$ 时，下式即 上式右半部分，于是

\[\begin {aligned} \sum _{d \mid n} \mu (d) &= (1 + (-1)) ^ m = 0 \end {aligned} \]
结束

于是显然有 $\sum _ {d \mid \gcd (i, j)} \mu (d) = [\gcd (i, j) = 1]$

积性函数

证明

显然 $\mu (1) = 1$，且若 $a, b$ 有等于 $1$ 的，容易证明 $\mu (a) \mu (b) = \mu (ab)$

显然，若 $a, b$ 中有满足 $\exist d > 1, d ^ 2 \mid x$，则 $ab$ 一定满足此条件

故 $\mu (ab) = \mu (a) \mu (b) = 0$，同样易得

只需考虑 $a, b$ 均为 最后一种情况 的情形

容易发现，$\omega (n)$ 是 加性函数，而 $-1$ 为常数，此形式符合 上文中提到的

加性函数 和 积性函数 的转化的式子形式，故 $\mu (n)$ 一定是 积性函数，得证
总质因数个数：$\Omega (n) = \sum _ {p \in \mathbb P} \sum _ {c \ge 1} [p ^ c \mid n]$

完全加性函数

证明（可以回顾 完全加性函数的判定，与加性函数 / 积性函数的判断有所不同）

先转化一下，有 $\Omega (n) = \sum _ {d \in \Z} [d \mid n] = \sum _ {p \in \mathbb P} \sum _ {c \ge 1} [p ^ c \mid n]$

显然有 $\Omega (1) = 0$，又由于 $p_i \in \mathbb P$，故易得 $\Omega (p_i) = 1$，然后颓狮子

\[\begin {aligned} \Omega (np_i) &= \sum _ {p \in \mathbb P} { \sum _ {c \ge 1} { [p ^ c \mid np_i] } } \\ &= \sum _ { p \in \mathbb P \and p \neq p_i } { \sum _ {c \ge 1} { [p ^ c \mid np_i] } } + \sum _ { c \ge 1 } { [p_i ^ c \mid np_i] } \\ &= \sum _ { p \in \mathbb P \and p \neq p_i } { \sum _ {c \ge 1} { [p ^ c \mid n] } } + \sum _ { c \ge 1 } { [p_i ^ c \mid np_i] } \\ &= \sum _ { p \in \mathbb P \and p \neq p_i } { \sum _ {c \ge 1} { [p ^ c \mid n] } } + \sum _ { c \ge 1 } { [p_i ^ c \mid n] } +1 \\ &= \sum _ {p \in \mathbb P} { \sum _ {c \ge 1} { [p ^ c \mid n] } } + 1 \\ &= \Omega (n) + \Omega (p_i) \end {aligned} \]
故得证，该函数为 完全加性函数

同理可知，总质因数和：$\Omega (n) = \sum _ {p \in \mathbb P} \sum _ {c \ge 1} p ^ c \times [p ^ c \mid n]$ 也是 完全加性函数
模意义下的乘法逆元：$n ^ {-1} \pmod p$

完全积性函数（$p \in \mathbb P$）

根据 余数的可乘性 即可证明，前面 同余关系 章节中应有 相关应用

更形式化的，显然有 $a ^ {-1} b ^ {-1} = (ab) ^ {-1} \pmod p$，并不要求 $a \perp b$
刘维尔函数：$\lambda (n) = (-1) ^ {\Omega (n)}$

完全积性函数

上文知，$\Omega (n)$ 是 完全加性函数，然后根据 加性函数 和 积性函数 的转化即可得

3. 线性筛积性函数

前面的素数部分，线性筛（欧拉筛） 筛素数的算法

提供了一个 线性筛特殊性质积性函数 在 $[1, n]$ 处 所有取值 的基本框架

只要 积性函数 $f$ 可以在 $O (1)$ 时间计算 任意质数幂 处的取值 $f (p ^ k)$，就适用 这个框架

这是一个 充分不必要 条件，有弱化条件，如 $O (k)$ 计算 $f (p ^ k)$ 也可以，但此处暂不提

bool Vis[MAXN];
int Pri[MAXN];
inline void Prime () {
	for (int i = 2; i <= N; ++ i) {
		if (!Vis[i]) Pri[++ Cnt] = 0;
		for (int j = 1; Pri[j] * i <= N && j <= Cnt; ++ j) {
			Vis[i * Pri[j]] = 1; 
			if (i % Pri[j] == 0) break ;
		}
	}
}

先来考虑 上述的线性筛 框架，容易发现 $Pri_i$ 显然与 $i$ 互质

于是我们可以在标记 $Vis$ 这一部分 算出对应的值

唯一的特例是枚举到 $i$ 的 最小质因数（即 $i \bmod Pri_j = 0$）时，此时不满足 $i \perp Pri_j$

我们需要把 $i$ 除尽其最小质因数，得到 $i'$，显然 $i' \perp Pri_i$，于是就可以算了

但是如果每次在 $i \bmod Pri_j = 0$ 时再来除的话，时间复杂度就会假

所以我们需要在过程中预处理每个数 $i$ 的 最小质因子 $p_i$ 的 最高次幂（$\max p_i ^ c$）

最后就得到了 下面的代码框架

inline void Sieve () {
	for (int i = 2; i <= N; ++ i) {
		if (!Vis[i]) Pri[++ Cnt] = i, F[i] = /* NOTE */, Low[i] = i;
		for (int j = 1; j <= Cnt && Pri[j] * i <= N; ++ j) {
			Vis[i * Pri[j]] = 1;
			if (i % Pri[j] == 0) {
				Low[i * Pri[j]] = Low[i] * Pri[j];
				if (i == Low[i]) F[i * Pri[j]] = /* NOTE */ // F[i = p_j ^ k] -> F[i * p_j = p_j ^ (k + 1)]
				else F[i * Pri[j]] = F[i / Low[i]] * F[Low[i * Pri[j]]];
				break ;
			}
			Low[i * Pri[i]] = Pri[j], F[i * Pri[j]] = F[i] * F[Pri[j]];
		}
	}
}