数论
01 / 共享的机制
很多题目底下其实藏着一层数论结构。一旦看出输入里真正存在的整除性 / 模 / 乘性结构, O(N) 的循环就坍缩成 O(log N) 或 O(N log log N)。 三个经典子模式:欧几里得求 GCD、按指数二进制位做快速幂、 用素数筛一次性标记所有合数。
01 / 一句话本质
每一轮把指数减半。exp 的二进制位决定哪些「平方项」会被乘进答案 —— O(log exp) 替代 O(exp)。题目计算 an mod Ma3n13M100
计算 3^13 mod 100。指数的二进制 = 1011(低位在前)。初始 result = 1,base = 3 % 100。
步
0 / 12
位 i
—
base
3
result
1
0 / 12
02 / 模式骨架
# 在 O(log exp) 内计算 (base^exp) mod Mresult ← 1base ← base % Mwhile exp > 0:if exp & 1: # exp 当前最低位为 1result ← (result × base) % Mbase ← (base × base) % M # 平方exp ← exp >> 1 # 丢掉刚用过的位return result
03 / 什么时候用这个模式
"large modular exponent / aⁿ mod M"
最经典的用法。LC 50(
pow(x, n) 浮点版,同样的骨架,多一步处理负指数), LC 372。看见 aⁿ mod M 且 n 大到无法直接循环 —— 就是它。"modular multiplicative inverse via Fermat's little theorem"
当模
p 是素数时,a⁻¹ ≡ a^(p−2) (mod p)。 一次快速幂即可得到逆元,无需扩展欧几里得 —— 这就是素数模下做「除法」的钥匙(组合数、计数问题里到处用)。"matrix exponentiation"
同样的骨架,把
× 换成矩阵乘法,result 初始化为单位矩阵。 这就是 O(k³ log N) 计算第 N 个 Fibonacci / 任意线性递推第 N 项的标准做法。"super-pow / nested exponent"
LC 372。当指数本身是一个巨大的数位数组
b = [b₀, b₁, …] 时,用 a^b = (a^(b/10))^10 · a^(b mod 10) 递归。每层只对一个 ≤ 10 的小指数做快速幂。04 / 常见坑
i.
乘法之后忘记
% M。base * base 已经在 [0, M²) 区间,不立刻取模,几次平方就会溢出 64 位整数。 模运算必须紧贴乘法发生处,而不是「最后再统一取模」。ii.
位为 0 时仍然把
result 乘进去。整个技巧的关键在于:只有
exp 中为 1 的位才贡献。 如果不加判断、无脑 result *= base,你算出来的其实是 base^(迭代次数),完全错了。乘法必须用 if exp & 1 守住。iii.
错误地特判
exp == 0。result 初值为 1,当 exp == 0 时循环根本不进入, 自然返回 1 —— 这也涵盖 0⁰ 这种约定为 1 的情形。 不要画蛇添足加一个「exp == 0 时返回 0」的分支。05 / 去 LeetCode 上练习
四道题。LC 50 是同一骨架的浮点版;其余几道都是「指数巨大、无法直接循环」的模幂场景。
— / 什么时候用哪个
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