数论知识体系

数论研究整数的乘法结构、同余结构与数论函数；
算法竞赛中的数论，则进一步关心这些结构如何被高效计算。

1 数论在数学体系中的位置

数论建立在集合、关系、映射与代数运算结构之上。

其中：

• 整除关系把正整数组织成偏序结构；
• 同余关系把整数划分为剩余类；
• 模乘法群描述可逆剩余类的乘法结构；
• 数论函数把整数的结构映射为可计算的数值；
• 狄利克雷卷积在因数分解上定义数论函数之间的乘法；
• 数论求和把这些结构转化为可以批量计算的算法。

在整个 240_Math 中，本专题主要回答：

1. 整数能够怎样分解；
2. 模意义下的方程如何求解；
3. 数论函数之间有什么结构；
4. 巨大指数、组合数和大整数如何计算；
5. 复杂的整除与 $\gcd$ 求和如何被化简。

返回：00_数学知识体系

---

2 整体知识主线

数论专题沿着以下主线展开：

整数的乘法结构 → 同余与线性方程 → 数论函数 → 模乘法群与指数结构 → 狄利克雷卷积与反演 → 数论求和 → 组合数取模 → 大整数质因数分解。

这条主线可以进一步分成四个层次。

2.1 整数的基础结构

研究整数由哪些基本单位组成，以及如何批量识别这些单位。

• 质数与合数；
• 算术基本定理；
• 因数结构；
• 试除法；
• 埃氏筛与线性筛。

对应：01_整数分解与筛法

2.2 模意义下的代数结构

研究整数在模数限制下的等式、除法与指数规律。

• 同余与剩余类；
• 裴蜀定理与扩展欧几里得；
• 乘法逆元；
• CRT 与 ExCRT；
• 欧拉定理、阶与原根；
• 离散对数与二次剩余。

对应：

• 02_同余方程与逆元
• 04_模意义下的指数问题

2.3 数论函数与求和结构

研究整数结构如何被数论函数描述，以及这些函数之间如何通过卷积与反演联系起来。

• 积性函数；
• 欧拉函数与莫比乌斯函数；
• 因数个数与因数和；
• 狄利克雷卷积；
• 莫比乌斯反演；
• 整除分块与杜教筛。

对应：

• 03_数论函数与线性筛
• 05_狄利克雷卷积与反演
• 06_数论求和

2.4 复合计算问题

综合使用前面的结构，处理更复杂的模运算与大整数问题。

• Lucas 与 ExLucas；
• 模质数幂的组合数；
• Miller–Rabin；
• Pollard–Rho。

对应：

• 07_组合数取模
• 08_大整数质因数分解

---

3 章节导航

3.1 整数分解与筛法

01_整数分解与筛法

研究整数的乘法结构，是整个数论专题的起点。

核心内容：

• 整除、因数与倍数；
• 质数与合数；
• 算术基本定理；
• 因数个数与因数和；
• 试除法；
• 埃氏筛；
• 线性筛。

主要用途：

• 判断质数；
• 分解较小整数；
• 预处理质数表；
• 为数论函数、模数分解和大整数分解提供基础。

3.2 同余方程与逆元

02_同余方程与逆元

以整数线性方程 $ax+by=c$ 为核心，把多种模方程统一起来。

核心内容：

• 同余与剩余类；
• 欧几里得算法；
• 裴蜀定理；
• 扩展欧几里得算法；
• 一次不定方程；
• 线性同余方程；
• 乘法逆元；
• CRT 与 ExCRT。

主要用途：

• 判断线性方程是否有解；
• 求解模意义下的除法；
• 合并多个同余条件；
• 为组合数取模和模指数问题提供基础。

3.3 数论函数与线性筛

03_数论函数与线性筛

研究数论函数、积性以及线性筛中的递推结构。

核心内容：

• 数论函数；
• 积性函数与完全积性函数；
• 质数幂上的局部贡献；
• 欧拉函数；
• 莫比乌斯函数；
• 因数个数与因数和；
• 线性筛的统一递推框架。

主要用途：

• 在 $O(N)$ 时间内批量预处理数论函数；
• 为反演、求和与杜教筛提供前置；
• 理解积性函数为什么可以按质数幂递推。

3.4 模意义下的指数问题

04_模意义下的指数问题

研究模乘法群中的幂、周期、生成与求逆。

核心内容：

• 完全剩余系与既约剩余系；
• 模乘法群；
• 欧拉定理与扩展欧拉定理；
• 元素的阶；
• 原根；
• BSGS 与 ExBSGS；
• 二次剩余与 Cipolla。

主要用途：

• 处理巨大指数；
• 求解模意义下的指数方程；
• 寻找原根；
• 计算模质数下的平方根。

3.5 狄利克雷卷积与反演

05_狄利克雷卷积与反演

研究数论函数之间的乘法结构，以及如何从因数求和中恢复原函数。

核心内容：

• 基本数论函数 $\varepsilon,1,\operatorname{id}$；
• 狄利克雷卷积；
• 卷积单位元与逆元；
• $\mu*1=\varepsilon$；
• $\varphi*1=\operatorname{id}$；
• 莫比乌斯反演；
• 构造 $\gcd$ 类求和中的卷积系数。

主要用途：

• 消去互质与 $\gcd$ 限制；
• 推导 $\gcd$、$\gcd^k$ 与质数 $\gcd$ 求和；
• 为杜教筛和数论求和提供统一语言。

3.6 数论求和

06_数论求和

研究卷积变形完成后，如何真正计算答案。

核心内容：

• 一维整除分块；
• 二维整除分块；
• 互质数对；
• $\gcd$ 与 $\gcd^k$ 求和；
• $\operatorname{lcm}$ 求和；
• 因数个数求和；
• 杜教筛；
• 加权杜教筛。

主要用途：

• 批量处理相同整除商；
• 计算数论函数前缀和；
• 解决大范围 $\gcd$、$\operatorname{lcm}$ 与因数类求和。

3.7 组合数取模

07_组合数取模

研究组合数在不同模数结构下的计算方法。

核心内容：

• 阶乘与阶乘逆元；
• Lucas 定理；
• Legendre 公式；
• 模质数幂的组合数；
• CRT 合并；
• ExLucas。

主要用途：

• 计算大规模组合数取模；
• 处理质数模数、质数幂模数与任意合数模数；
• 综合使用逆元、质因数分解与 CRT。

3.8 大整数质因数分解

08_大整数质因数分解

研究 long long 范围内的大整数素性判定与质因数分解。

核心内容：

• 大整数模乘；
• Miller–Rabin；
• Pollard–Rho；
• 递归质因数分解。

主要用途：

• 判断大整数是否为质数；
• 求大整数的非平凡因子；
• 求最大质因子或完整质因数分解；
• 为大模数的 ExLucas 提供分解工具。

---

4 知识依赖关系

八篇内容并不是彼此独立的。

4.1 基础依赖

• 01_整数分解与筛法 是所有章节的基础；
• 02_同余方程与逆元 支撑 04、07；
• 03_数论函数与线性筛 支撑 05、06；
• 05_狄利克雷卷积与反演 支撑 06；
• 08_大整数质因数分解 可以为 07 中的大模数分解提供工具。

4.2 推荐阅读顺序

第一次系统阅读时，建议按照编号顺序：

01 → 02 → 03 → 04 → 05 → 06 → 07 → 08。

若只为了算法竞赛快速补充，可以按目标选择支线：

• 基础模运算：01 → 02 → 04；
• 数论求和：01 → 03 → 05 → 06；
• 组合数取模：01 → 02 → 07；
• 大整数分解：01 → 08。

---

5 按问题定位

5.1 判断与分解整数

问题	对应笔记
判断较小整数是否为质数	01_整数分解与筛法
批量筛出 $1$ 到 $N$ 的质数	01_整数分解与筛法
分解较小整数	01_整数分解与筛法
判断 long long 范围的大整数是否为质数	08_大整数质因数分解
分解大整数	08_大整数质因数分解

5.2 求解模方程

问题	对应笔记
求 $ax+by=c$ 的整数解	02_同余方程与逆元
求 $ax\equiv c\pmod m$	02_同余方程与逆元
求乘法逆元	02_同余方程与逆元
合并多个同余方程	02_同余方程与逆元
求 $a^x\equiv b\pmod m$	04_模意义下的指数问题
求 $x^2\equiv n\pmod p$	04_模意义下的指数问题

5.3 预处理数论函数

问题	对应笔记
线性筛 $\varphi,\mu$	03_数论函数与线性筛
线性筛因数个数与因数和	03_数论函数与线性筛
理解积性函数的递推	03_数论函数与线性筛
计算函数卷积	05_狄利克雷卷积与反演

5.4 处理数论求和

问题	对应笔记
$\sum\lfloor n/i\rfloor$	06_数论求和
互质数对计数	05_狄利克雷卷积与反演、06_数论求和
$\gcd=k$ 计数	05_狄利克雷卷积与反演、06_数论求和
$\gcd$、$\gcd^k$ 求和	05_狄利克雷卷积与反演、06_数论求和
$\operatorname{lcm}$ 求和	06_数论求和
杜教筛	06_数论求和

5.5 组合数取模

模数与数据范围	对应方法
质数模数，$n$ 较小	阶乘与阶乘逆元
质数模数，$n$ 很大	Lucas
模数为 $p^k$	模质数幂组合数
模数为任意合数	ExLucas

对应：07_组合数取模

---

6 数学正文、模板库与题型库的边界

数论内容同时存在于三个不同位置，但它们承担不同职责。

6.1 240_Math

这里保存数学正文，主要回答：

• 概念是什么；
• 条件为什么存在；
• 公式如何推导；
• 算法为什么成立；
• 不同内容之间怎样连接。

代码只保留解释当前算法所必需的部分。

6.2 Math 模板库

模板库保存可以直接调用或快速默写的实现。

这里更关注：

• 函数接口；
• 变量命名；
• 数据类型；
• 复杂度；
• 代码可靠性。

数学正文中的重复公共函数可以写成：

ll qpow( ll a, ll k, ll mod ) { /* 模板代码略 */ }

避免在每篇笔记中重复展开。

6.3 220_Library

题型库保存具体问题的识别与转化方式。

例如：

• 互质点对；
• $\gcd=k$；
• 质数 $\gcd$；
• $\operatorname{lcm}$ 求和；
• $\tau(ij)$；
• 各类 Lucas 与 ExLucas 题型。

这里更关注：

• 如何识别题型；
• 如何选择公式；
• 如何从题目条件完成建模；
• 代码在具体数据范围下如何调整。

---

7 当前专题状态

当前数论主干已经覆盖：

• 整数分解；
• 同余理论；
• 数论函数；
• 模指数结构；
• 卷积与反演；
• 数论求和；
• 组合数取模；
• 大整数质因数分解。

暂时没有单独展开的内容包括：

• 高次同余方程；
• $p$ 进数与局部方法；
• 代数数论；
• 更一般的群论与有限域；
• 复杂生成函数与乘法变换。

这些内容并非当前算法竞赛主线所必需，可以在以后出现明确需求时再补充。

---

8 学习与复习方式

第一次学习一篇内容时，按照以下顺序：

概念 → 地位 → 用途 → 核心原理 → 代码实现。

复习时则反过来：

1. 看到问题后判断它属于哪一类结构；
2. 找到对应结论与使用条件；
3. 回忆关键公式或递推；
4. 再进入模板库确认实现。

数论题最容易出现的问题通常不是“不会模板”，而是：

• 没有识别模数结构；
• 忽略互质条件；
• 在逆元不存在时仍然进行除法；
• 混淆线性筛的两个递推分支；
• 找到了卷积变形，却没有对应前缀和；
• 使用整除分块时没有同时固定所有整除商；
• 把 Pollard–Rho 找到的合因子误认为质因子。

因此，每次使用公式时都应同时检查它的前提。