算法基础 — 初等数论与组合
从整数的性质出发，理解同余、不定方程等数论基础，再走进组合数学的世界，体会数学中"离散"的美感。
一、整除进阶
整除的基本概念
如果整数 a 除以整数 b (b ≠ 0) 的商是整数且余数为 0，我们就说 b 整除 a，记作 b | a。例如 3 | 12，因为 12 ÷ 3 = 4 是整数。
带余除法
对于任意整数 a 和正整数 b，存在唯一的整数 q（商）和 r（余数），使得：
带余除法
a = bq + r, 0 ≤ r < b
例：求 37 除以 5 的商和余数。
37 = 5 × 7 + 2，所以商 q = 7，余数 r = 2。
验证：0 ≤ 2 < 5，满足条件。
最大公约数（GCD）与辗转相除法
最大公约数（Greatest Common Divisor，简称 GCD）是指两个或多个正整数共有的约数中最大的一个。例如 gcd(12, 18) = 6。
对正整数 a、b，求最大公约数最经典的方法是辗转相除法（欧几里得算法，Euclidean Algorithm），其核心思想是：
辗转相除法原理
gcd(a, b) = gcd(b, a mod b) (其中 a mod b 表示 a 除以 b 的余数，且 a、b 为正整数)
反复运用，直到余数为 0，此时的除数即为最大公约数。
例：计算 gcd(84, 60)。
84 = 60 × 1 + 24 → gcd(84, 60) = gcd(60, 24)
60 = 24 × 2 + 12 → gcd(60, 24) = gcd(24, 12)
24 = 12 × 2 + 0 → gcd(24, 12) = 12
所以 gcd(84, 60) = 12。
最小公倍数（LCM）
最小公倍数（Least Common Multiple，简称 LCM）是两个或多个正整数公有的倍数中最小的一个。例如 lcm(4, 6) = 12。
GCD 与 LCM 的关系
gcd(a, b) × lcm(a, b) = a × b (a、b 为正整数)
例：已知 gcd(12, 18) = 6，求 lcm(12, 18)。
由公式：lcm(12, 18) = 12 × 18 ÷ gcd(12, 18) = 216 ÷ 6 = 36。
二、同余基础
同余的定义
在数论中，同余（Congruence）是描述两个整数除以同一个数后余数相等的关系。
同余的定义
如果整数 a 和 b 除以正整数 m 的余数相同，则称 a 与 b 关于模 m 同余，记作
a ≡ b (mod m)
等价于 m | (a − b)，即 m 整除 a − b。
例：判断 37 与 13 是否关于模 12 同余。
37 − 13 = 24，24 能被 12 整除，所以 37 ≡ 13 (mod 12)。
验证：37 ÷ 12 = 3 余 1，13 ÷ 12 = 1 余 1，余数相同。
同余的性质
同余关系具有以下重要性质：
同余的性质（设 a ≡ b (mod m), c ≡ d (mod m)）
自反性：a ≡ a (mod m)
对称性：若 a ≡ b (mod m)，则 b ≡ a (mod m)
传递性：若 a ≡ b (mod m) 且 b ≡ c (mod m)，则 a ≡ c (mod m)
可加性：a + c ≡ b + d (mod m)
可减性：a − c ≡ b − d (mod m)
可乘性：a × c ≡ b × d (mod m)
例：已知 17 ≡ 5 (mod 12)，8 ≡ 20 (mod 12)，则：
17 + 8 = 25，5 + 20 = 25，25 ≡ 25 (mod 12) ✓
17 × 8 = 136，5 × 20 = 100，136 − 100 = 36 = 3 × 12 ✓
同余思想的本质：把无限多的整数按照除以 m 的余数分成 m 个等价类（称为剩余类），每个类中的数两两同余。这样一来，很多大数的计算可以"模掉"m 来简化。
三、一次不定方程
问题引入
在实际问题中，我们经常会遇到"找两个整数 x、y，使 ax + by = c 成立"的问题。这样的方程有无限多组解（如果有的话），所以称为不定方程。
二元一次不定方程的一般形式
ax + by = c (其中 a、b、c 是已知整数，a、b 不全为 0)
有解的条件
方程 ax + by = c 有整数解的充要条件是：
有解条件
gcd(a, b) | c （即 c 能被 gcd(a, b) 整除）
例：判断 3x + 5y = 7 是否有整数解。
gcd(3, 5) = 1，而 1 | 7，所以方程有整数解。
事实上，我们可以找到一组特解：x = 4, y = −1（因为 3×4 + 5×(−1) = 12 − 5 = 7）。
例：判断 2x + 4y = 3 是否有整数解。
gcd(2, 4) = 2，而 2 ∤ 3（2 不能整除 3），所以方程没有整数解。
特解与通解
如果 (x0, y0) 是方程的一组特解，那么全部整数解（通解）为：
通解公式
x = x0 + (b / d) · t
y = y0 − (a / d) · t
其中 d = gcd(a, b)，t 为任意整数。
例：已知 3x + 5y = 7 的一组特解为 (4, −1)，求通解。
d = gcd(3, 5) = 1，所以：
x = 4 + 5t, y = −1 − 3t (t ∈ ℤ)
验证 t = 1：x = 9, y = −4，3×9 + 5×(−4) = 27 − 20 = 7 ✓
验证 t = −1：x = −1, y = 2，3×(−1) + 5×2 = −3 + 10 = 7 ✓
A：3×1 + 5×1 = 3 + 5 = 8 ≠ 7 ✗
B：3×2 + 5×1 = 6 + 5 = 11 ≠ 7 ✗
C：3×4 + 5×(−1) = 12 − 5 = 7 ✓
由于 gcd(3,5)=1 整除 7，方程必有解，D 错误。选 C。
四、容斥原理与抽屉原理
容斥原理（Inclusion-Exclusion Principle）
容斥原理是计数中处理"重叠"情况的利器。当我们需要计算多个集合的并集中的元素个数时，直接相加会重复计数重叠的部分，需要"容"（包含）再"斥"（排除）。
两个集合的容斥原理
|A ∪ B| = |A| + |B| − |A ∩ B|
例：某班 40 人中，喜欢数学的有 25 人，喜欢物理的有 20 人，两科都喜欢的有 10 人。问至少喜欢一科的有多少人？
设 A = {喜欢数学的人}，B = {喜欢物理的人}。
|A ∪ B| = |A| + |B| − |A ∩ B| = 25 + 20 − 10 = 35 人。
三个集合的容斥原理
|A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|
例：某班 50 人，参加数学竞赛 20 人，物理竞赛 15 人，化学竞赛 10 人，同时参加数学和物理的 8 人，数学和化学的 5 人，物理和化学的 3 人，三科都参加的 2 人。问至少参加一科的有多少人？
|M ∪ P ∪ C| = 20 + 15 + 10 − 8 − 5 − 3 + 2 = 31 人。
抽屉原理（Pigeonhole Principle）
抽屉原理（又称鸽巢原理）是最基本的组合数学原理之一，它描述了一个非常直观的现象：
抽屉原理（第一形式）
如果把 n + 1 个物品放入 n 个抽屉中，那么至少有一个抽屉里有至少两个物品。
抽屉原理（推广形式）
如果把 m 个物品放入 n 个抽屉中（m > n），那么至少有一个抽屉里有至少 ⌈m / n⌉ 个物品。
（其中 ⌈x⌉ 表示不小于 x 的最小整数）
例 1（基础）：367 个人中，至少有两个人在同一天过生日。
一年最多 366 天（闰年），367 个人放入 366 个"生日抽屉"，由抽屉原理知结论成立。
例 2（推广）：把 10 个苹果放入 3 个抽屉，至少有一个抽屉里有多少个苹果？
⌈10 / 3⌉ = ⌈3.33⌉ = 4 个。
五、图论入门
图的基本要素
图（Graph）是组合数学中最基本的结构之一，它由顶点（Vertex）和边（Edge）组成。图论研究的是顶点之间如何通过边相互连接。
图 G = (V, E)
V 是顶点的集合（非空），E 是边的集合。
每条边连接两个顶点（可以是同一个顶点——此时称为"自环"）。
有向图与无向图
无向图
边没有方向，用线段连接两个顶点。
如朋友关系图——A 认识 B 等价于 B 认识 A。
边用 (u, v) 表示，其中 (u, v) = (v, u)
有向图
边有方向，用箭头表示。
如微博关注关系——A 关注 B 不意味着 B 关注 A。
边用 <u, v> 表示，<u, v> ≠ <v, u>
基本概念
| 概念 | 含义 | 示例 |
|---|---|---|
| 顶点数 |V| | 图中顶点的总个数 | 3 个顶点即 |V| = 3 |
| 边数 |E| | 图中边的总条数 | 连接 3 个顶点的三角形有 3 条边 |
| 度 deg(v) | 与顶点 v 关联的边端数；无向图中的一条自环贡献 2 | 三角形中每个顶点度为 2 |
| 路径 | 相邻顶点均有边连接且顶点不重复的序列 | A → B → C 是一条路径 |
| 回路 | 首尾顶点相同、其余顶点不重复的闭合序列 | A → B → C → A |
| 连通图 | 任意两个顶点之间都有路径 | 树、完全图都是连通的 |
例：一个完全图 K4（4 个顶点，每两个顶点之间都有一条边）有多少条边？
4 个顶点中任选 2 个连边，边的数量 = C(4, 2) = 6 条。
一般地，n 个顶点的完全图有 C(n, 2) = n(n−1) / 2 条边。
图的表示
图可以用邻接矩阵或邻接表来表示：
邻接矩阵
一个 n × n 的矩阵 A，
A[i][j] = 1 表示顶点 i 到 j 有边，
A[i][j] = 0 表示无边。
无向图的邻接矩阵是对称的。
邻接表
为每个顶点维护一个列表，
列出与该顶点相邻的所有顶点。
适合表示稀疏图（边数远小于 n²）。
六、进阶数论与几何组合
欧拉函数 φ(n)
欧拉函数 φ(n)（Euler's totient function）指的是小于或等于 n 的正整数中与 n 互质的数的个数。
欧拉函数的定义
φ(n) = |{ k | 1 ≤ k ≤ n, gcd(k, n) = 1 }|
例 1：计算 φ(6)。
1 到 6 中，与 6 互质的数有：1, 5（因为 gcd(2,6)=2, gcd(3,6)=3, gcd(4,6)=2, gcd(6,6)=6）
所以 φ(6) = 2。
例 2：计算 φ(12)。
1 到 12 中，与 12 互质的数有：1, 5, 7, 11（共 4 个）。
所以 φ(12) = 4。
欧拉函数的计算公式
若 n 的质因数分解为 n = p1e1 · p2e2 · … · pkek，则
φ(n) = n · (1 − 1/p1) · (1 − 1/p2) · … · (1 − 1/pk)
例：用公式计算 φ(12)。
12 = 22 × 3
φ(12) = 12 × (1 − 1/2) × (1 − 1/3) = 12 × 1/2 × 2/3 = 4 ✓
几何组合初步：皮克定理
皮克定理（Pick's Theorem）给出了格点多边形面积与内部和边界上格点个数之间的优美关系。
皮克定理
对于一个顶点都在格点（坐标均为整数的点）上的简单多边形，
S = I + B / 2 − 1
其中 S 是多边形的面积，I 是内部格点的个数，B 是边界（含顶点）上格点的个数。
例：求以 (0,0)、(4,0)、(0,3) 为顶点的三角形面积，并用皮克定理验证。
直接计算：直角三角形，两直角边长 4 和 3，面积 S = 4 × 3 / 2 = 6。
数格点：
边界格点 B：在 (0,0)→(4,0) 上有 5 个（含端点），(0,0)→(0,3) 上有 4 个，(4,0)→(0,3) 上只有 2 个端点，重复计数的 3 个顶点各算一次，B = 5 + 4 + 2 − 3 = 8。
内部格点 I：可直接数出来——(1,1)、(2,1)、(1,2) 共 3 个。
皮克定理验证：S = I + B / 2 − 1 = 3 + 8/2 − 1 = 3 + 4 − 1 = 6 ✓
皮克定理的美妙之处：它把几何量（面积）与数论量（格点个数）联系起来，是"数形结合"的一个经典范例。皮克定理只对格点多边形成立，且要求多边形是简单的（不自交）。
用皮克定理验证：边界格点 B = 8，内部格点 I = 3，S = I + B/2 − 1 = 3 + 4 − 1 = 6。选 B。