数学题概览：GCD、筛法与数论基础

为什么数学题是底层架构设计的必考项

数学题不像数据结构题那样有固定套路，它考察的是数学直觉和从公式到代码的转化能力。这些问题能够区分「背题者」和「真正理解算法」的候选人——因为数学题很难靠背解法应付，必须理解原理才能写出正确代码。

LeetCode 数学题的核心考点大致分为五类：

欧几里得算法：GCD 的核心

最大公约数（GCD，Greatest Common Divisor） 是两个整数共有因数中最大的那个。GCD 的用途远不止「求约数」——很多看似无关的题目背后都藏着 GCD：

• 字符串中最长公因子（LeetCode 1071）
• 行程问题（步长是两个间距的 GCD）
• 分数化简（分子分母同除以 GCD）

为什么辗转相除法是正确的

欧几里得算法的核心等式：

gcd(a, b) = gcd(b, a % b)

直觉上这不那么显然。让我们来理解为什么：

如果 d 是 a 和 b 的公约数（d | a 且 d | b），那么：

a = q·b + r  （其中 r = a % b）

由于 d | a 且 d | b，所以 d | (a - q·b) = d | r。
反过来，如果 d | b 且 d | r，则 d | (q·b + r) = d | a。

因此 {a, b 的公约数} = {b, r 的公约数}，两者的最大值相等，即 gcd(a, b) = gcd(b, a % b)。

Java 实现

// 递归版（经典）
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 迭代版（避免递归栈溢出，实际更常用）
int gcd(int a, int b) {
    while (b != 0) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

// 最小公倍数（LCM）
long lcm(long a, long b) {
    return a / gcd(a, b) * b;  // 先除后乘，防止溢出
}

复杂度分析：每次递归 b 至少缩小到原来的一半（菲波那契数列是最坏情况），所以递归深度是 O(log min(a, b))。

拓展：多个数的 GCD

// 数组中所有元素的最大公约数
int gcdOfArray(int[] nums) {
    int g = nums[0];
    for (int x : nums) g = gcd(g, x);
    return g;
}

gcd(a, b, c) = gcd(gcd(a, b), c)，这个性质让我们可以线性扫描。

质数筛法：从暴力到 O(n) 线性筛

质数（素数） 是只有 1 和自身两个因数的大于 1 的正整数。判断质数的三种方法，复杂度逐级优化：

朴素试除法

判断单个数 n 是否为质数，只需枚举到 √n：

boolean isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; (long)i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

为什么只需枚举到 √n？
如果 n 有因数 d > √n，则 n/d < √n 也是因数，所以在枚举到 √n 时必定已经找到了更小的那个因数。

复杂度：O(√n)，适合判断单个数是否为质数。

埃拉托斯特尼筛法（埃氏筛）

生成 [2, n] 范围内所有质数的经典算法，思路形象地叫「筛子」：从最小的质数 2 开始，把它所有的倍数都划掉，再取下一个没被划掉的数（必然是质数），继续划掉它的倍数……

筛出 [2, 20] 内所有质数的过程：

初始：2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20

划去 2 的倍数（从 2×2=4 开始）：
     2  3  X  5  X  7  X  9  X   11  X   13  X   15  X   17  X   19  X

划去 3 的倍数（从 3×3=9 开始）：
     2  3  X  5  X  7  X  X  X   11  X   13  X   X   X   17  X   19  X

4 已被划去，5×5=25>20，停止

结果：2, 3, 5, 7, 11, 13, 17, 19

// 埃氏筛：返回 [2, n] 内所有质数
List<Integer> sieve(int n) {
    boolean[] notPrime = new boolean[n + 1];
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        if (!notPrime[i]) {
            primes.add(i);
            // 从 i*i 开始，避免重复（更小的倍数已被更小的质数标记）
            for (long j = (long)i * i; j <= n; j += i) {
                notPrime[(int)j] = true;
            }
        }
    }
    return primes;
}

复杂度：O(n log log n)。这个结论来自调和级数：标记过程中的操作次数约等于 n/2 + n/3 + n/5 + ... ≈ n·ln(ln n)。

埃氏筛的局限：合数可能被多次标记（如 12 会被 2 和 3 各标记一次），这是它无法达到 O(n) 的原因。

线性筛（欧拉筛）

线性筛确保每个合数只被标记一次，从而达到严格的 O(n)：

// 线性筛：每个合数只被其最小质因数标记一次
int[] linearSieve(int n) {
    boolean[] notPrime = new boolean[n + 1];
    int[] primes = new int[n / (int)(Math.log(n) + 1) + 10];  // 预分配
    int cnt = 0;

    for (int i = 2; i <= n; i++) {
        if (!notPrime[i]) {
            primes[cnt++] = i;  // i 是质数
        }
        // 用已知质数标记合数
        for (int j = 0; j < cnt && (long)i * primes[j] <= n; j++) {
            notPrime[i * primes[j]] = true;
            if (i % primes[j] == 0) {
                // 关键：primes[j] 是 i 的最小质因数
                // 继续枚举会导致重复标记，及时退出
                break;
            }
        }
    }
    return Arrays.copyOf(primes, cnt);
}

为什么 break 保证了每个合数只被标记一次？

当 primes[j] | i 时，对于下一个质数 primes[j+1]，乘积 i * primes[j+1] 最小质因数是 primes[j]（因为 primes[j] | i），所以应该由 (i / primes[j]) * primes[j+1] 在外层循环枚举 i / primes[j] 时来标记它。此时继续枚举会造成重复，用 break 剪枝。

快速幂：O(log n) 计算大指数

计算 x^n 的直觉方法是连乘 n 次，O(n)。但当 n 达到 10^9 时，这种方式完全不可行。

二进制分解思想

任何整数 n 都可以表示为 2 的幂次之和（二进制展开）：

n = 13 = 1101₂ = 8 + 4 + 1

x^13 = x^(8+4+1)
     = x^8 · x^4 · x^1

x^1, x^2, x^4, x^8 可以从 x^1 开始逐步平方得到，
每次平方只需 1 次乘法，共需 O(log n) 次

// 快速幂迭代版（处理负指数）—— LeetCode 50
public double myPow(double x, int n) {
    long N = n;
    if (N < 0) { x = 1.0 / x; N = -N; }  // 负指数转化

    double result = 1.0;
    while (N > 0) {
        if ((N & 1) == 1) result *= x;  // n 的当前位是 1，累乘
        x *= x;                          // x 平方，对应下一个二进制位
        N >>= 1;                         // 处理下一位
    }
    return result;
}

执行过程示意（以 x^13 为例）：

N = 13 = 1101₂, x = x

step1: N&1=1, result *= x¹, x=x², N=6 (110₂)
step2: N&1=0,               x=x⁴, N=3 (11₂)
step3: N&1=1, result *= x⁴, x=x⁸, N=1 (1₂)
step4: N&1=1, result *= x⁸, N=0

result = x¹ · x⁴ · x⁸ = x^13  ✓

模快速幂（整数场景）

题目要求 x^n mod p 时，在每步乘法后取模：

// 模快速幂 —— 整数版，结果对 mod 取余
long powMod(long base, long exp, long mod) {
    long result = 1;
    base %= mod;
    while (exp > 0) {
        if ((exp & 1) == 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

数字规律类题型

这类题不需要复杂算法，靠找规律 + 数学推导。

快乐数（LeetCode 202）——Floyd 判圈

快乐数的变换序列要么以 1 结尾（快乐数），要么会进入循环（非快乐数）。用快慢指针判圈：

public boolean isHappy(int n) {
    int slow = n, fast = digitSquareSum(n);
    while (fast != 1 && slow != fast) {
        slow = digitSquareSum(slow);
        fast = digitSquareSum(digitSquareSum(fast));
    }
    return fast == 1;
}

private int digitSquareSum(int n) {
    int sum = 0;
    while (n > 0) {
        int d = n % 10;
        sum += d * d;
        n /= 10;
    }
    return sum;
}

丑数（LeetCode 264）——三路归并

丑数是只含质因数 2、3、5 的正数（1 是第一个丑数）。前 n 个丑数按顺序排列，可以用三个指针分别维护「下一个乘以 2/3/5 还未使用的丑数」：

public int nthUglyNumber(int n) {
    int[] dp = new int[n];
    dp[0] = 1;
    int p2 = 0, p3 = 0, p5 = 0;  // 三个指针指向「候选基底」

    for (int i = 1; i < n; i++) {
        int next2 = dp[p2] * 2, next3 = dp[p3] * 3, next5 = dp[p5] * 5;
        dp[i] = Math.min(next2, Math.min(next3, next5));
        // 哪个被选中，对应指针前进（注意：可能同时有多个相等，都要前进）
        if (dp[i] == next2) p2++;
        if (dp[i] == next3) p3++;
        if (dp[i] == next5) p5++;
    }
    return dp[n - 1];
}

为什么三个 if 而不是 else if？
因为可能有多个相等（如 6 = 2×3，同时被 p2 和 p3 产生），必须同时推进，否则会产生重复。

核心架构问题汇总