本讲定位：五级的开篇，也是整个五级的基础工具箱。官方大纲把「初等数论」列为五级第一个知识块，内容量是所有知识块里最大的，本讲和五级第 02 讲合起来才讲得完。gcd 和取模是后面高精度、二分、分治里反复出现的零件。
对应官方大纲：五级知识块 1「初等数论」的前半部分——素数与合数（概念先行，详见五级第 02 讲）、最大公约数与最小公倍数、同余与模运算、约数与倍数、奇偶性、欧几里得算法。同时涉及知识块 2「算法复杂度估算（含对数）」。
前置知识：四级全部内容。特别是四级第 04 讲的递推与四级第 01 讲的函数。
代码说明：本讲代码均已用 g++ 11.5（
-std=c++11）编译运行验证，文中所有数值结论均为程序实际输出。
四级考”你会不会用 C++“，五级考”你会不会想算法”。这一讲就是分水岭的第一课。
举个例子感受一下差距：
求两个数的最大公约数。
四级学生的思路：从 $\min(a,b)$ 往下枚举，找到第一个同时整除 $a$ 和 $b$ 的数。
for (int i = min(a, b); i >= 1; i--)
if (a % i == 0 && b % i == 0) { cout << i; break; }
$O(\min(a,b))$——$a,b$ 到 $10^9$ 时必然超时。
五级学生的思路：欧几里得算法，三行代码，$O(\log \min(a,b))$——$10^9$ 也只要约 30 步。
同一个问题，从”能算出来”到”算得够快”，这就是五级要求的跃迁。数据范围会明确告诉你该用哪一种（见五级第 05 讲）。
整除：若存在整数 $k$ 使得 $a = b \times k$（$b \ne 0$），称 $b$ 整除 $a$，记作 $b \mid a$。
此时称：
⚠️ 符号方向别记反：$b \mid a$ 读作”$b$ 整除 $a$”，竖线左边是约数，右边是倍数。$3 \mid 12$ 是对的，$12 \mid 3$ 是错的。选择题会用这个符号出题。
代码判断：if (a % b == 0) 表示 $b \mid a$。