初等数论学习笔记 III：数论函数与筛法 _生活百科

初等数论学习笔记 I：同余相关。
初等数论学习笔记 II：分解质因数。

1. 数论函数本篇笔记所有内容均与数论函数相关。因此充分了解各种数论函数的名称，定义，符号和性质是必要的。
1.1 相关定义

数论函数：定义域为正整数的函数称为数论函数。因其在所有正整数处均有定义，故可视作数列。OI 中常见的数论函数的陪域（即可能的取值范围）为整数。
加性函数：若对于任意 \(a, b\in \mathbb{N}_+\) 且 \(a\perp b\) 均有 \(f(ab) = f(a) + f(b)\)，则称 \(f\) 为加性函数。注意区分代数中的加性函数。
积性函数：若对于任意 \(a, b\in \mathbb{N}_+\) 且 \(a\perp b\) 均有 \(f(ab) = f(a)f(b)\)，则称 \(f\) 为积性函数。易知 \(f(1) = 1\) 是必要条件。
完全积性函数：若对于任意 \(a, b\in \mathbb{N}_{+}\) 均有 \(f(ab) = f(a)f(b)\)，则称 \(f\) 为完全积性函数。完全积性函数一定是积性函数。
数论函数的加法：对于数论函数 \(f, g\) ， \(f + g\) 表示 \(f\) 和 \(g\) 对应位置相加，即 \((f + g)(x) = f(x) + g(x)\) 。
数论函数的数乘：对于数 \(c\) 和数论函数 \(f\)，\(c\cdot f\) 表示 \(f\) 的各个位置乘 \(c\)，即 \((c\cdot f)(x) = c \cdot f(x)\) 。一般简记作 \(cf\) 。
数论函数的点乘：对于数论函数 \(f, g\)，\(f \cdot g\) 表示 \(f\) 和 \(g\) 对应位置相乘，即 \((f \cdot g)(x) = f(x)g(x)\) 。为与狄利克雷卷积符号 \(*\) 作区分，点乘符号通常不省略。

1.2 常见数论函数设 \(n\) 的唯一分解为 \(\prod\limits_{i = 1} ^ m p_i ^ {c_i}\)，以下是一些常见数论函数：

单位函数：\(\epsilon(n) = [n = 1]\) 。当 \(n = 1\) 时取值为 \(1\)，否则取值为 \(0\) 。它是完全积性函数。
常数函数：\(1(n) = 1\) 。它是完全积性函数。
恒等函数：\(\mathrm{id}_k(n) = n ^ k\) 。\(\mathrm{id}_1(n)\) 记作 \(\mathrm {id}(n)\) 。它是完全积性函数。
除数函数：\(\sigma_k(n) = \sum\limits_{d\mid n}d ^ k\) 。\(\sigma_0(n)\) 表示 \(n\) 的约数个数，记作 \(\tau(n)\) 或 \(d(n)\) 。\(\sigma_1(n)\) 表示 \(n\) 的约数和，记作 \(\sigma(n)\) 。\(\sigma_k(n)\) 有计算式 \(\begin{cases} \prod\limits_{i = 1} ^ m (c_i + 1) & k = 0 \\ \sum\limits_{i = 1} ^ m \frac{p_i ^ {(c_i + 1)k} - 1}{p_i - 1} & k > 0\end{cases}\)：根据乘法分配律，\(n\) 的所有约数的 \(k\) 次方之和可写作 \(\prod\limits_{i = 1} ^ m\sum\limits_{j = 0} ^ {c_i} p_i ^ {jk}\) ，等比数列求和后即得。
欧拉函数：\(\varphi(n) = \sum\limits_{i = 1} ^ n[i\perp n]\) ，表示 \(n\) 以内与 \(n\) 互质的数的个数。关于欧拉函数的性质，详见笔记 I.
本质不同质因子个数函数：\(\omega(n) = \sum\limits_{p \in \mathbb{P}} [p\mid n]\)，表示 \(n\) 的本质不同质因子个数。
莫比乌斯函数：\(\mu(n) = \begin{cases} 1 & n = 1 \\ 0 & \exists d > 1, d ^ 2\mid n \\ (-1) ^ {\omega(n)} & \mathrm{otherwise} \end{cases}\) 。

以上所有函数除 \(\omega\) 是加性函数以外，其余均为积性函数。根据计算式及积性函数的定义易证。
2. 素数筛法素数筛法是数论体系中最基本的知识点，几乎所有数论题目都需要筛出 \(1\sim n\) 的所有素数。
2.1 埃氏筛素数埃氏筛用所有已经筛出的素数的倍数标记合数：从 \(2\) 到 \(n\) 枚举所有数 \(i\) ，若 \(i\) 未被标记，则 \(i\) 是质数，将 \(i\) 除 \(i\) 以外的倍数标记为合数。
for(int i = 2; i < N; i++)if(!vis[i]) {pr[++cnt] = i;for(int j = 2 * i; j < N; j += i) vis[j] = 1;}常数优化：根据合数 \(i\) 的最小质因子 \(\leq \sqrt i\)，可以从 \(i ^ 2\) 开始标记。

for(int i = 2; i < N; i++)if(!vis[i]) {pr[++cnt] = i;if(1ll * i * i < N) // 防止 i * i 溢出导致 REfor(int j = i * i; j < N; j += i) vis[j] = 1;}

【初等数论学习笔记 III：数论函数与筛法】埃氏筛的精髓在于其复杂度证明：不超过 \(n\) 的质数的倒数之和为 \(\mathcal{O}(\ln \ln n)\) 级别。
\[\sum\limits_{p\in \mathbb{P}, p\leq n} \dfrac 1 p = \mathcal{O}(\ln \ln n)\]这说明埃氏筛的复杂度为 \(\mathcal{O}(n\ln \ln n)\) 。
证明来自戴江齐学长：
因为每个数只会被其素因子筛到，所以 \(\sum\limits_{p\in \mathbb{P}, p\leq n} \dfrac 1 p = \sum\limits_{i = 1} ^ n \omega(i)\) 。
根据 \(d(i)\) 的计算式， \(\sum\limits_{i = 1} ^ n 2 ^ {\omega(i)} \leq \sum\limits_{i = 1} ^ n d(i)= \mathcal{O}(n\ln n)\) 。
根据 \(2 ^ x\) 的凸性和琴生不等式得 \(\sum\limits_{i = 1} ^ n 2 ^ {\omega(i)} \geq n 2 ^ {\frac{\sum_{i = 1} ^ n \omega(i)} n}\)，所以 \(2 ^ {\frac{\sum_{i = 1} ^ n \omega(i)} n} \leq \mathcal{O}(\ln n)\) 。