数学算法基础：取模、GCD、快速幂与素数筛

以前看到“数学算法基础：取模、GCD、快速幂与素数筛”，我会下意识去找一份模板保存下来。后来发现这样学得很快，忘得也快，因为我一看到取模、最大公约数和快速幂就觉得是数学题，写代码时才发现真正容易错的是溢出、边界和运算顺序。所以这篇不从标准答案起步，而是顺着我当时的疑问一点点往下拆。

算法里的数学基础不需要一上来就钻很深，但必须掌握常见模型：取模、最大公约数、快速幂、素数判断、组合计数。这些内容经常隐藏在数组、动态规划、图论和字符串题里。

它从哪里来

算法中的数学基础有很长历史。欧几里得算法两千多年前就用反复相除求最大公约数；素数筛与模运算也来自古典数论。现代程序只是把这些确定步骤放到有限整数和大规模输入中重新实现。

数学算法路线

$数学算法学习路线$

图：数学算法重点是把公式写成可控、可验证的代码

取模与溢出

很多计数题答案很大，需要对 1_000_000_007 取模。

static final long MOD = 1_000_000_007L;

long add(long a, long b) {
    return (a + b) % MOD;
}

long multiply(long a, long b) {
    return (a % MOD) * (b % MOD) % MOD;
}

如果两个数都接近 int 上限，乘法很容易溢出，所以乘法中间结果通常用 long。

最大公约数

欧几里得算法用辗转相除求最大公约数。

int gcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return Math.abs(a);
}

最小公倍数可以通过 a / gcd(a, b) * b 计算，先除再乘可以降低溢出风险。

快速幂

快速幂把指数按二进制拆分，复杂度从 O(n) 降到 O(log n)。

long fastPow(long base, long exp, long mod) {
    long ans = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if ((exp & 1) == 1) {
            ans = ans * base % mod;
        }
        base = base * base % mod;
        exp >>= 1;
    }
    return ans;
}

它常用于大指数取模、组合数学、矩阵快速幂等场景。

素数筛

如果只判断一个数是否为素数，可以试除到平方根；如果要批量判断 1..n 的素数，埃氏筛更合适。

boolean[] sieve(int n) {
    boolean[] prime = new boolean[n + 1];
    Arrays.fill(prime, true);
    if (n >= 0) prime[0] = false;
    if (n >= 1) prime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (!prime[i]) continue;
        for (int j = i * i; j <= n; j += i) {
            prime[j] = false;
        }
    }
    return prime;
}

从 i * i 开始筛，是因为更小的倍数已经被更小的因子筛过。

组合计数

组合问题常见于 DP 和数学题。最稳的入门方式是先理解杨辉三角。

long[][] comb(int n) {
    long[][] c = new long[n + 1][n + 1];
    for (int i = 0; i <= n; i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++) {
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
        }
    }
    return c;
}

如果需要取模，转移时加 % MOD。如果 n 很大，还要考虑阶乘和逆元。

我的分析

数学题最怕“公式会背，代码写炸”。我的习惯是把数学代码当成基础设施来写：先处理边界，再处理溢出，最后用几个极端用例验证。比如 0、1、负数、大数、重复取模，都要单独想一遍。

面试题

为什么求最小公倍数建议先除再乘？
快速幂为什么是 O(log n)？
埃氏筛为什么可以从 i * i 开始？
取模运算中减法可能出现负数时怎么处理？
组合数用 DP、阶乘逆元分别适合什么规模？