数论

01 / 共享的机制

很多题目底下其实藏着一层数论结构。一旦看出输入里真正存在的整除性 / 模 / 乘性结构, O(N) 的循环就坍缩成 O(log N) 或 O(N log log N)。三个经典子模式:欧几里得求 GCD、按指数二进制位做快速幂、用素数筛一次性标记所有合数。

01 / 一句话本质

gcd(a, b) = gcd(b, a % b) —— 同时整除 a 和 b 的数也一定整除余数,所以可以不断用更小的余数替换原值而不丢答案。每一步 pair 都按几何级数下降,log(min(a, b)) 次迭代就结束。LCM 顺势而出:a / gcd(a, b) · b。

题目求 gcd(a, b) 与 lcm(a, b)a24b36

从 a = 24、b = 36 开始。反复使用 gcd(a, b) = gcd(b, a % b),直到 b = 0。

步

0 / 5

gcd

—

lcm

—

0 / 5

a, b

02 / 模式骨架

# 欧几里得 GCD —— 在右操作数为 0 时终止def gcd(a, b):while b ≠ 0:a, b ← b, a % b # 缩小return a# LCM —— 先除再乘,避免溢出def lcm(a, b):return a / gcd(a, b) · b

"最大公约数 / 公因数"

最经典的用法。LC 1071 —— 「能同时整除两个字符串的最大字符串」化归为对两个长度求 GCD。只要问题里出现「公因子」「公约数」或「能同时容纳两者的最大单位」,就找欧几里得。

"最小公倍数 / 周期"

需要找同时被 a 与 b 整除的最小数时用 —— 同步周期、重复信号、「两个事件最早一起发生在何时」。先求 gcd,再算 a / gcd · b —— 先除后乘可以避免 a · b 溢出。

"分数是否最简 / 是否互素"

两个数互素当且仅当 gcd(a, b) = 1。把 p/q 化为最简分数,只要一次 GCD 加两次除法。有理数键的哈希不变量、Stern–Brocot 树导航、Farey 邻居 —— 都立足于此。

"对整个数组求 GCD"

LC 1979。{a₁, …, aₙ} 的 gcd 等于 gcd(…gcd(gcd(a₁, a₂), a₃)…, aₙ) —— 两两折叠。中间值只可能不增, 一旦降到 1 就可以早停;总工作量仍被各次归约的开销之和所界定。

按 a · b / gcd(a, b) 算 LCM 而没有先除。

先乘后除在 32 位整型上会溢出 —— 即便 64 位,若 a、b 接近 2³¹ 也可能炸。永远先除:a / gcd(a, b) · b。这次除法是精确的(gcd 整除 a),顺序安全, 且中间值不会超过最终答案。

ii.

忘记 b == 0 的终止条件。

没有这层保护,要么死循环(a % 0 未定义或抛异常), 要么更糟 —— 第一步就因为 b == 0 触发除零崩溃。按定义 gcd(a, 0) = a,让这种情形从循环里自然落出。

iii.

负数输入时结果的符号。

约定俗成 gcd 取非负值;某些语言的内建 %(如 C) 的符号跟随被除数,递归中可能落到负的 a 上。入口处统一取 abs(a)、abs(b),或者用语言里数学风格的模运算。 Python 的 % 跟随除数符号,可直接使用;C/Java 不行。

四道题。前三题是欧几里得归约的直接应用;最后一题借助 Bézout 恒等式 ——gcd(a, b) 是能写成 a·x + b·y 的最小正整数 —— 判定可行性。

GCD / LCM

问题核心是整除性时用 —— 公因数、是否互素、最简分数、由 a · b / gcd(a, b) 求 LCM。欧几里得恒等式 gcd(a, b) = gcd(b, a % b) 每一步都呈几何级数下降。

欧几里得 · LC 1071 · LC 1979

模幂

要计算 aⁿ mod M(n 极大)或质数模下的乘法逆元时用。每步把指数减半;n 的二进制位决定哪些平方项会被乘进答案。O(log n) 替代 O(n)。

指数减半 · LC 50 · LC 372

素数筛

需要所有不超过 N 的素数(或所有最小素因子)时用。对每个素数 p, 把它的所有倍数标记为合数;每个合数被标记的次数摊销下来是 O(log log N)。

埃氏筛 · LC 204 · LC 952