数论基础 (Number Theory)¶

数论是算法竞赛中理论性与技巧性兼具的重要板块，包含模运算、最大公约数、同余方程与素数筛法。

快速幂与模运算 (Modular Exponentiation)¶

计算 \(a^b \pmod m\)，时间复杂度 \(\mathcal{O}(\log b)\)。

long long power(long long a, long long b, long long mod) {
    long long res = 1 % mod;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = (__int128)res * a % mod;
        a = (__int128)a * a % mod;
        b >>= 1;
    }
    return res;
}

扩展欧几里得算法 (Extended GCD / Bezout 等式)¶

求解二元一次不定方程 \(ax + by = \gcd(a, b)\) 的一组整数特解 \((x, y)\)。

// 返回 gcd(a, b)，并通过引用带回一组整数解 x, y
long long extgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long g = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return g;
}

乘法逆元 (Modular Inverse)¶

当 \(ax \equiv 1 \pmod m\) 时，\(x\) 称为 \(a\) 模 \(m\) 的乘法逆元，记作 \(a^{-1}\)。

费马小定理 (模数 p 为质数且 a 不是 p 的倍数)扩展欧几里得求逆元 (适用于任意互质模数 m)线性递推求 1 到 n 的逆元

根据费马小定理：\(a^{p-1} \equiv 1 \pmod p \implies a \cdot a^{p-2} \equiv 1 \pmod p\)，故逆元为 \(a^{p-2} \bmod p\)。

long long inv_fermat(long long a, long long p) {
    return power(a, p - 2, p);
}

long long inv_extgcd(long long a, long long m) {
    long long x, y;
    long long g = extgcd(a, m, x, y);
    if (g != 1) return -1; // 不存在逆元
    return (x % m + m) % m;
}

在 \(\mathcal{O}(n)\) 时间内预处理出 \(1 \sim n\) 的所有逆元：

\[ \text{inv}[i] = (p - \lfloor p / i \rfloor) \cdot \text{inv}[p \bmod i] \pmod p \]

std::vector<long long> get_invs(int n, long long p) {
    std::vector<long long> inv(n + 1, 0);
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) {
        inv[i] = (p - p / i) * inv[p % i] % p;
    }
    return inv;
}

欧拉筛法 (线性筛质数与欧拉函数)¶

在严格 \(\mathcal{O}(n)\) 时间复杂度内筛出 \(1 \sim n\) 范围内的所有质数以及欧拉函数 \(\phi(x)\)。

#include <vector>

void linear_sieve(int n, std::vector<int> &primes, std::vector<bool> &is_prime, std::vector<int> &phi) {
    is_prime.assign(n + 1, true);
    phi.assign(n + 1, 0);
    is_prime[0] = is_prime[1] = false;
    phi[1] = 1;

    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            phi[i] = i - 1;
        }
        for (int p : primes) {
            if (i * p > n) break;
            is_prime[i * p] = false;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p;
                break; // 保证每个合数只被其最小质因数筛除一次
            } else {
                phi[i * p] = phi[i] * (p - 1);
            }
        }
    }
}

LeetCode 经典真题精选与题解提示¶

LeetCode 204 - 计数质数 (Count Primes) 中等
提示

素数筛法标准模板题。
- 统计小于非负整数 \(n\) 的质数数量。
- 采用埃氏筛（\(\mathcal{O}(n \log \log n)\)）或欧拉线性筛（\(\mathcal{O}(n)\)）。外层只需遍历到 \(\sqrt{n}\)，合数标记从 \(i \times i\) 开始可有效消除重复标记。
LeetCode 372 - 超级次方 (Super Pow) 中等
提示

快速幂递归拆解 / 欧拉降幂。
- 指数以数组形式给出 \(b = [b_0, b_1, \dots, b_k]\)。利用幂模性质拆分递归：\(a^{[b_0, \dots, b_k]} \equiv (a^{[b_0, \dots, b_{k-1}]})^{10} \times a^{b_k} \pmod{1337}\)。
- 亦可直接运用扩展欧拉定理：先求出 \(\phi(1337) = 1140\)，将高精大整数指数对 \(\phi(m)\) 取模降幂后单次快速幂计算。
LeetCode 878 - 第 N 个神奇数字 (Nth Magical Number) 困难
提示

二分答案 + 容斥原理 + 最小公倍数 (LCM)。
- 求第 \(n\) 个能被 \(a\) 或 \(b\) 整除的数。随着数值 \(x\) 增大，能被整除的数字个数严格单调递增，具有二分单调性。
- 在区间 \([1, \min(a, b) \times n]\) 上二分数值 \(x\)。根据容斥原理，小于等于 \(x\) 的神奇数字个数为：\(f(x) = \lfloor x/a \rfloor + \lfloor x/b \rfloor - \lfloor x/\text{lcm}(a, b) \rfloor\)，其中 \(\text{lcm}(a, b) = (a \times b) / \gcd(a, b)\)。
LeetCode 829 - 连续整数求和 (Consecutive Numbers Sum) 困难
提示

等差数列求和与数论因式分解。
- 设 \(n\) 能表示为长度为 \(k\) 的连续正整数之和：\(n = x + (x + 1) + \dots + (x + k - 1) = kx + \frac{k(k - 1)}{2}\)（其中 \(x \ge 1\) 为整数）。
- 变形可得 \(kx = n - \frac{k(k - 1)}{2} > 0\)。因此 \(x\) 为正整数的充要条件为：\((n - \frac{k(k - 1)}{2}) \bmod k == 0\)。
- 从 \(k = 1\) 开始枚举项数，只要 \(\frac{k(k - 1)}{2} < n\)（即 \(k \le \mathcal{O}(\sqrt{2n})\)）时检验整除性并累加答案。