数学算法

数学算法专题涵盖了最基础的数论（GCD/LCM）、质数判断、快速幂以及大数运算等。

基础数论

1. 最大公约数 (GCD) - 辗转相除法

$gcd(a, b) = gcd(b, a \text{ mod } b)$

public int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 迭代版本
public int gcdIter(int a, int b) {
    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

2. 最小公倍数 (LCM)

$lcm(a, b) = (a \times b) / gcd(a, b)$

质数与计数

1. 判断质数 (Naive)

只需判断到 $\sqrt{n}$ 即可。

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

2. 质数筛 (Sieve of Eratosthenes)

求 1 到 n 所有的质数。时间复杂度 O(n log log n)。

public int countPrimes(int n) {
    boolean[] isPrime = new boolean[n];
    Arrays.fill(isPrime, true);
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (isPrime[i]) {
            count++;
            // 标记所有的倍数
            if ((long)i * i < n) {
                for (int j = i * i; j < n; j += i) isPrime[j] = false;
            }
        }
    }
    return count;
}

快速幂与快速乘

求 $a^n \text{ mod } m$。时间复杂度 O(log n)。

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

练习

1. LeetCode 204：计数质数
2. LeetCode 50：Pow(x, n) (快速幂)
3. LeetCode 172：阶乘后的零 (数学规律)
4. LeetCode 372：超级次方 (快速幂 + 递归)
5. 实现 大数相加、大数相乘 的逻辑。