数学基础

GCD & LCM

欧几里得算法：gcd(a, b) = gcd(b, a % b)，终止条件 b = 0 时返回 a。时间 O(log min(a,b))。LCM = a / gcd(a,b) * b（先除后乘防溢出）。

// GCD (Euclidean algorithm)
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int lcm(int a, int b) { return a / gcd(a, b) * b; } // divide first!

// C++17: #include <numeric>
// int g = std::gcd(a, b), l = std::lcm(a, b);

典型题目

• 149. 直线上最多的点数（坡度化简为 dy/gcd, dx/gcd）
• 365. 水壶问题（贝祖定理：若 z 能被 gcd(x,y) 整除则可行）
• 1979. 找出数组的最大公因数（所有元素的 gcd）

C++ 内置：C++17 起 '<'numeric'>' 提供 std::gcd(a,b) 和 std::lcm(a,b)，可直接使用。

质数筛

埃氏筛（Sieve of Eratosthenes）：初始化所有数为质数，从 2 开始将每个质数的倍数标记为合数。O(n log log n)。线性筛（欧拉筛）严格 O(n) 且每个合数只被标记一次。

// Sieve of Eratosthenes — O(n log log n)
vector<bool> sieve(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; (long long)i * i <= n; i++)
        if (isPrime[i])
            for (int j = i * i; j <= n; j += i)
                isPrime[j] = false;
    return isPrime;
}

典型题目

• 204. 计数质数（筛法）
• 2523. 范围内最接近的两个质数（筛后查找）
• 279. 完全平方数（四平方和定理：所有正整数均可表示为 ≤ 4 个完全平方数之和）

逐个试除：单个数判质数用试除法：只需试除到 √n，O(√n)。批量判断用筛法。

快速幂（二进制取幂）

计算 a^b (mod m)：将指数 b 写成二进制，反复平方基数，遇到 1 位则乘入结果。时间 O(log b)。

// Fast exponentiation (binary exponentiation) — a^b mod m
long long powmod(long long a, long long b, long long m) {
    long long res = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

// Modular inverse (when m is prime): a^(-1) mod m = a^(m-2) mod m
long long inv(long long a, long long m) { return powmod(a, m - 2, m); }

典型题目

• 50. Pow(x, n)（处理负指数和整数溢出）
• 372. 超级次方（循环节 + 快速幂）
• 1680. 连接连续二进制数字（模运算 + 快速移位）

模逆元：当模数 p 为质数时，a 的模逆元 = pow(a, p-2, p)（费马小定理），用于除法取模：a/b mod p = a * b^(p-2) mod p。

模运算技巧

模运算分配律：(a+b)%m = ((a%m)+(b%m))%m，乘法类似。注意：C++ 的 % 对负数可能返回负值，需 ((a%m)+m)%m 保证非负。

常用公式

• (a + b) % m = ((a % m) + (b % m)) % m
• (a * b) % m = ((a % m) * (b % m)) % m
• (a - b + m) % m // 防止减法出负数
• a / b mod m = a * inv(b) mod m // 除法转乘模逆元

典型题目

• 509/70. 斐波那契 / 爬楼梯（大数取模）
• 62. 不同路径（组合数 C(m+n-2, m-1) 取模）
• 1922. 统计好数字的数目（快速幂 + 模）

long long 溢出：两个 int 相乘可能超 int 范围（约 2×10^9），先转 (long long) 再取模：(long long)a * b % m。