数学 · 数论三大基础

1. 核心原理

数论在面试里高频但范围窄，主要围绕三件套：质数筛、快速幂、最大公约数。本章把这三件工具的定义、性质和复杂度推导讲清楚，第 §2 节给统一模板，第 §3 节用 LC 204 计数质数把"筛法"这一件落地。

最大公约数与欧几里得算法

两个非负整数 a, b 的最大公约数 gcd(a, b) 是同时整除它们的最大正整数（约定 gcd(a, 0) = a）。欧几里得（Euclid）算法基于一条恒等式：

gcd(a, b) = gcd(b, a mod b)     (b > 0)

证明只用到一行：设 d | a 且 d | b，则 d | (a - kb) = a mod b；反之亦然。所以 (a, b) 和 (b, a mod b) 共享同一组公约数，最大公约数自然相等。

收敛速度：可以证明每两步 a mod b < a / 2——若 b ≤ a/2，下一轮 a mod b < b ≤ a/2 直接成立；若 b > a/2，则 a mod b = a - b < a/2。所以经过 2 log₂ a 步必然到 b = 0，复杂度 O(log min(a, b))。

最小公倍数：lcm(a, b) = a / gcd(a, b) × b。先除后乘避免 a × b 中间溢出。多个数的 lcm 用结合律 lcm(a, b, c) = lcm(lcm(a, b), c)。

模逆元与扩展欧几里得

在模 m 下，a 的乘法逆元是满足 a × x ≡ 1 (mod m) 的 x，记作 a⁻¹。存在性：a⁻¹ mod m 存在当且仅当 gcd(a, m) = 1（裴蜀定理）。

实际算法有两条路线：

• 模数是质数（如 10⁹ + 7）：由费马小定理 a^(p-1) ≡ 1 (mod p)，所以 a⁻¹ ≡ a^(p-2) (mod p)。套快速幂 O(log p) 解决。
• 模数非质数：用扩展欧几里得 exgcd(a, m) 求解 a × x + m × y = 1，x mod m 即逆元。

素数筛：埃氏筛与线性筛

判断单个数是否质数用 O(√n) 试除即可。但要"找出 [2, n] 内所有质数"，逐个试除是 O(n √n)，n = 5 × 10⁶ 时 ≈ 10¹⁰ 步必 TLE。筛法把每个合数只标记常数次，整体砍到近线性。

埃氏筛（Sieve of Eratosthenes）：维护布尔数组 is_prime[0..n]，从小到大扫 i，若 is_prime[i] 为真则 i 是质数，把 i², i² + i, i² + 2i, ... 全部标为合数。从 i² 而非 2i 起步是因为 2i, 3i, ..., (i-1)i 已被更小的质数标过。

复杂度推导：内层循环总操作数 = Σ_{p ≤ n, p 质数} n/p，根据 Mertens 定理这个和约为 n × ln ln n，故复杂度 O(n log log n)。n = 5 × 10⁶ 时 ≈ 2 × 10⁷ 步，毫秒级。

线性筛（Euler / Linear Sieve）：保证每个合数恰好被它的最小质因子标一次，复杂度严格 O(n)。关键多一行 if i % primes[j] == 0: break——一旦 primes[j] 是 i 的最小质因子，再往下用更大的 primes[j+1] 标记 i × primes[j+1] 会让这个合数被一个非最小质因子标记到，必须停。

下面这个交互演示走一遍 n = 20 上的埃氏筛过程：

< 20 的质数：2, 3, 5, 7, 11, 13, 17, 19，共 8 个。

快速幂

直接计算 a^b 需 b - 1 次乘法，b = 10¹⁸ 时不可行。把指数 b 按二进制分解：

b = b_{k-1} ... b_1 b_0  (二进制)
a^b = ∏_{i: b_i = 1} a^(2^i)

预计算 a, a², a⁴, a⁸, ...（每个由前一个平方得到），把对应二进制位为 1 的部分相乘，总共 O(log b) 次乘法。

带模数版本——加减乘对模 m 满足分配律 (x × y) mod m = ((x mod m) × (y mod m)) mod m，每步取模即可，结果不会膨胀。

2. 通用模板

三件套各自的最小骨架。注意 C++ / Java 中的乘法可能溢出 int，统一用 long/long long。

# 1. 线性筛 (Linear Sieve)
def linear_sieve(n):
    """返回 [0, n) 内的质数列表"""
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    primes = []
    for i in range(2, n):
        if is_prime[i]:
            primes.append(i)
        for p in primes:
            if i * p >= n:
                break
            is_prime[i * p] = False
            if i % p == 0:                    # 关键：保证最小质因子
                break
    return primes


# 2. 快速幂（含模运算）
def pow_mod(a, b, m=None):
    """a^b 或 a^b mod m"""
    result = 1
    a = a % m if m else a
    while b > 0:
        if b & 1:
            result = result * a
            if m:
                result %= m
        a = a * a
        if m:
            a %= m
        b >>= 1
    return result


# 3. gcd
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

// 1. 线性筛
int[] linearSieve(int n) {
    boolean[] isPrime = new boolean[n];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    int[] primes = new int[n];
    int cnt = 0;
    for (int i = 2; i < n; i++) {
        if (isPrime[i]) primes[cnt++] = i;
        for (int j = 0; j < cnt && (long) i * primes[j] < n; j++) {
            isPrime[i * primes[j]] = false;
            if (i % primes[j] == 0) break;
        }
    }
    return Arrays.copyOf(primes, cnt);
}

// 2. 快速幂模
long powMod(long a, long b, long m) {
    long result = 1;
    a %= m;
    while (b > 0) {
        if ((b & 1) == 1) result = result * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return result;
}

// 3. gcd
long gcd(long a, long b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 1. 线性筛
vector<int> linearSieve(int n) {
    vector<bool> isPrime(n, true);
    isPrime[0] = isPrime[1] = false;
    vector<int> primes;
    for (int i = 2; i < n; i++) {
        if (isPrime[i]) primes.push_back(i);
        for (int p : primes) {
            if ((long long)i * p >= n) break;
            isPrime[i * p] = false;
            if (i % p == 0) break;                  // 关键：保证最小质因子
        }
    }
    return primes;
}

// 2. 快速幂模（用 long long 防溢出）
long long powMod(long long a, long long b, long long m) {
    long long result = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) result = result * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return result;
}

// 3. gcd
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

几点要说明：

• 线性筛的 break：if i % primes[j] == 0: break 保证后续 i × primes[j+1], i × primes[j+2], ... 的最小质因子都不是 primes[j+1]，由更大的 i' 在以后某轮去筛。漏掉这行就退化成埃氏筛。
• 快速幂溢出：Python 任意精度无忧；Java / C++ 中 a * a 在 a 接近 10⁹ 时溢出 int，必须 long。m ≤ 10⁹ 时 long 安全（10⁹ × 10⁹ = 10¹⁸ < 2⁶³）；m ≥ 10¹⁰ 要用 __int128 或 Python。
• gcd 的负数：gcd(-a, b) 数学上定义为 gcd(|a|, |b|)，Python 的 % 对负数返回非负余数所以模板自动正确；Java / C++ 的 % 对负数返回负余数，要在入口处 a = Math.abs(a)。

3. 母题精讲

LeetCode 204. 计数质数

链接：LeetCode 204

题目（中文翻译）：给一个整数 n，返回所有严格小于 n 的质数的数量。

数据范围：

• 0 ≤ n ≤ 5 × 10⁶

示例：

输入：n = 10
输出：4
解释：< 10 的质数有 2, 3, 5, 7。

输入：n = 0
输出：0

暴力解：逐个试除

最朴素的写法是对 2 到 n-1 的每个 i，试除 2 到 √i：

class Solution:
    def countPrimes_brute(self, n: int) -> int:
        def is_prime(x):
            if x < 2:
                return False
            for k in range(2, int(x ** 0.5) + 1):
                if x % k == 0:
                    return False
            return True
        return sum(1 for i in range(n) if is_prime(i))

时间 O(n √n)。n = 5 × 10⁶ 时约 1.1 × 10¹⁰ 次操作，TLE。

低效来源很明显：6 被 2 整除时，12, 18, 24, ... 还要再各自试除一次 2。把"已经被整除过"的位置一次性标掉，每个合数只被标一次，复杂度立刻下来。

线性筛解

直接套 §2 线性筛模板：

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 2:
            return 0
        is_prime = [True] * n
        is_prime[0] = is_prime[1] = False
        primes = []
        for i in range(2, n):
            if is_prime[i]:
                primes.append(i)
            for p in primes:
                if i * p >= n:
                    break
                is_prime[i * p] = False
                if i % p == 0:
                    break
        return len(primes)

时间 O(n)，空间 O(n)。在 n = 5 × 10⁶ 量级下约 5 × 10⁶ 步，毫秒级。

Follow-up：上面是筛法，处理"枚举范围内所有质数"。如果题目改成"算 2^100 mod 10⁹ + 7"——指数中等但模数大，怎么办？这就引到 §4.1 LC 50 的快速幂。

4. 例题

4.1 LC 50 Pow(x, n)

链接：LeetCode 50

题意：实现 pow(x, n)，即计算 x 的 n 次幂。n 可正可负。

数据范围：

• x：−100.0 到 100.0
• n：−2³¹ 到 2³¹ − 1
• x 不为 0 时 x^n 在 −10⁴ 到 10⁴ 之间

示例：

输入：x = 2.00000, n = 10
输出：1024.00000

输入：x = 2.00000, n = -2
输出：0.25000 (= 1 / 2² = 1 / 4)

思路：快速幂。注意 n 可能是负数，先把它变成正数 + 倒数。也要注意 n = -2³¹ 取反会溢出 Java/C++ int（绝对值变成 2³¹，超出 int 范围），用 long 或 Python 任意精度规避。

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = -n
        result = 1.0
        while n > 0:
            if n & 1:
                result *= x
            x *= x
            n >>= 1
        return result

复杂度 O(log |n|)。Python 的 ** 运算符内部也是快速幂（甚至更聪明的算法），但面试要白板手写。

Follow-up：上面 n 是 int。如果 n 是个大整数数组（每位 0-9），还要模上 1337 呢？这是 LC 372。

4.2 LC 372 超级次方

链接：LeetCode 372

题意：给一个正整数 a 和一个 1D 数组 b（每个元素 0-9 表示 b 的一位十进制数字），返回 a^b mod 1337。

数据范围：

• 1 ≤ a ≤ 2³¹ − 1
• b.length 1 到 2000

示例：

输入：a = 2, b = [1, 0]
输出：1024 (= 2^10)

输入：a = 2, b = [3]
输出：8

思路：当指数本身是数组形式（可能上千位）时，用恒等式

a^(10 * x + y) mod m = ((a^x mod m)^10 mod m) × (a^y mod m) mod m

从 b[0] 开始递推：每处理一位，把当前结果 r 变成 r^10 × a^{b[i]}，全程模 1337。

class Solution:
    def superPow(self, a: int, b: list[int]) -> int:
        MOD = 1337

        def pow_mod(x, n):
            x %= MOD
            r = 1
            while n > 0:
                if n & 1:
                    r = r * x % MOD
                x = x * x % MOD
                n >>= 1
            return r

        result = 1
        for digit in b:                       # b 是从高位到低位
            result = pow_mod(result, 10) * pow_mod(a, digit) % MOD
        return result

复杂度 O(len(b) × log 10) ≈ 2000 × 4，毫秒级。

注意 1337 = 7 × 191 不是质数，所以不能用费马小定理求循环节。但快速幂的"位分解"思路不依赖模数是否质数，照样跑得动。

5. 边界、易错与复杂度

筛法的几个细节

埃氏筛从 i² 开始而不是 2i：i 之前的倍数 2i, 3i, ..., (i-1) × i 已经被 2, 3, ..., i-1 这些更小的质数标过。从 i² 开始是优化常数（不影响渐近复杂度）。

线性筛的核心 break：if i % p == 0: break 保证 i × p 的最小质因子是 p，且每个合数恰好被它的最小质因子标一次。少了这个 break 就退化成埃氏筛。

空间换时间：is_prime[] 占 O(n) 空间。n = 10⁸ 时 100MB——LC 一般不会逼到这个量级。空间紧张时可以用 bitset 把空间砍 8 倍。

快速幂的两个陷阱

b = 0 边界：a^0 = 1（任何数的 0 次幂是 1，含 0）。模板里的循环条件 while b > 0 自然处理。

b 为负：a^(-b) = 1 / a^b。整数题里 b ≥ 0，浮点 / 实数题（如 LC 50）才会遇到。

乘法溢出：模幂里 a * a 在大 a 下可能溢出。Python 任意精度无忧；Java/C++ 用 long 或 __int128；Go 用 int64 在 m ≤ 10⁹ 时安全（10⁹ × 10⁹ = 10¹⁸ < 2⁶³）。

gcd 的两个变体

最大公约数：gcd(a, b) = gcd(b, a mod b)。基础情形 gcd(a, 0) = a。

最小公倍数：lcm(a, b) = a / gcd(a, b) × b。先除后乘避免溢出。

多个数的 gcd：gcd(a, b, c) = gcd(gcd(a, b), c)。可以 reduce 一遍数组。

复杂度速查

7. 这套工具下一步在哪里出现

本章学到的几个原子操作——筛法、快速幂、gcd / exgcd / 模逆元——在站内其他章节有大量下游复用：

面试常被追问的方向

数论题在 LC / 面试里追问通常落在这几个方向：

模逆元怎么选（费马小 vs exgcd）：

• 模数 p 是质数且 gcd(a, p) = 1 → 费马小 a^(p-2) mod p，一行快速幂搞定
• 模数不是质数（例如题目要 mod 一个合数）→ 必须用 exgcd：a * x + p * y = 1 中 x 即为 a⁻¹ mod p

def exgcd(a: int, b: int) -> tuple[int, int, int]:
    """returns (g, x, y) s.t. a*x + b*y = g = gcd(a, b)"""
    if b == 0:
        return a, 1, 0
    g, x1, y1 = exgcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def mod_inv(a: int, mod: int) -> int:
    g, x, _ = exgcd(a, mod)
    if g != 1:
        raise ValueError(f"inverse of {a} mod {mod} does not exist")
    return x % mod

质数判定大整数 (n ≥ 10¹⁸)：试除法 O(√n) 直接挂；用 Miller-Rabin 概率测试，固定基数 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] 对 n < 3.3 × 10²⁴ 完全可靠。LC 里少见但面试系统设计有时会问。

GCD 二进制变体（Stein 算法）：把欧几里得里的 % 换成位移：用 gcd(a, b) = 2·gcd(a/2, b/2) 当两者偶、gcd(a, b) = gcd(a/2, b) 当一偶一奇。位移和减法代替模运算，硬件友好——CPython 大整数下反而慢，但 C++ / Rust 上 1.5-2x 提升。

同框架筛法：埃氏 / 欧拉筛能改造成同时筛最小质因子 lpf、欧拉函数 phi、Möbius mu——一遍 O(n) 把整个数论函数表全部预处理出来。

8. 小结

数论三件套——筛法、快速幂、gcd——覆盖面试里大部分基础数论题。筛法预处理小范围内的质数表；快速幂把 O(b) 砍到 O(log b)，配合模运算解决大指数问题；gcd 是欧几里得算法 + 它的字符串 / 模逆元变体。三个工具单独熟练后，复合题（如 LC 1922 = 快速幂 + 计数）自然能拼出来。

对应灵神题单：数论 / 筛法 / 快速幂 / gcd

进一步阅读：LeetCode 数学题单 / 灵茶山艾府数学专题