第 7 章：基础数论 (Basic Number Theory)

在比赛中，数论题通常只有两个极端：

1. 一眼题：只要你知道公式，3分钟写完 AC。
2. 结论题：你不知道那个定理，想破脑袋也做不出来。

本章我们只讲最实用、出场率最高的三个工具。

7.1 欧几里得算法：GCD 与 LCM

7.1.1 最大公约数 (GCD)

怎么求两个数 $a$ and $b$ 的最大公约数？ 小学老师教过“短除法”，但那个太慢了。计算机使用辗转相除法 (Euclidean algorithm)。

核心原理：$\text{gcd}(a, b) = \text{gcd}(b, a \bmod b)$。 一直把余数变成新的除数，直到余数为 0。

代码模板 (必背)：

// 递归写法：简单优雅
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
 
// C++17 自带库函数 (需 #include <numeric>)
// int res = std::gcd(a, b); 

7.1.2 最小公倍数 (LCM)

公式非常简单： $\text{lcm}(a, b) = \frac{a \times b}{\text{gcd}(a, b)}$

⚠️ 致命坑点： 如果你写 int lcm = a * b / gcd(a, b);，你很可能会 WA。 因为 $a \times b$ 可能会先溢出 int 范围，然后再除以 gcd，导致结果错误。

正确写法：先除后乘。

long long lcm(int a, int b) {
    // 必须转成 long long 防止溢出
    return (1LL * a / gcd(a, b)) * b; 
}

7.2 素数 (Prime) 的判定与筛选

素数是只能被 1 和它本身整除的数（1 不是素数，2 是最小的素数）。

7.2.1 试除法：判断一个数是不是素数

场景：给你一个数 $N$ ($N \le 10^{12}$)，判断它是否为素数。

思路：从 $2$ 遍历到 $N-1$，看能不能整除？ 优化：只需要遍历到 $\sqrt{N}$。因为因子是成对出现的，如果 $\sqrt{N}$ 之前没有因子，后面也不可能有了。

bool isPrime(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i * i <= n; i++) { // i*i <= n 代替 i <= sqrt(n)
        if (n % i == 0) return false;
    }
    return true;
}

复杂度：$O(\sqrt{N})$。

7.2.2 埃氏筛法 (Sieve of Eratosthenes)：批量找素数

场景：要把 $1 \sim N$ ($N \le 10^6$) 范围内所有的素数都找出来。 如果你对每个数都跑一遍上面的 isPrime，复杂度是 $O(N\sqrt{N})$，太慢了。

思路：

1. 准备一个布尔数组 vis，一开始假设全是素数。
2. 从 2 开始，把 2 的倍数（4, 6, 8...）全部标记为“非素数”。
3. 找到下一个没被标记的数（3），它是素数，把 3 的倍数（6, 9, 12...）全标记掉。
4. 重复直到 $\sqrt{N}$。

const int MAXN = 1000005;
bool vis[MAXN]; // vis[i] = true 表示 i 已经被筛掉（不是素数）
 
void sieve(int n) {
    vis[0] = vis[1] = true; // 0 和 1 不是素数
    for (int i = 2; i * i <= n; i++) {
        if (!vis[i]) { // 如果 i 是素数
            // 把 i 的倍数全划掉
            // 从 i*i 开始划（因为 2*i, 3*i 已经被前面的数划过了）
            for (int j = i * i; j <= n; j += i) {
                vis[j] = true;
            }
        }
    }
}

复杂度：$O(N \log \log N)$，非常接近线性，对于 $10^6$ 毫无压力。

进阶：还有一个 欧拉筛 (Euler Sieve / Linear Sieve)，是 $O(N)$ 的，适合 $N=10^7$ 的极端情况。初学者先掌握埃氏筛足够了。

7.3 模运算与快速幂 (Modular Arithmetic)

你经常会看到题目要求：“结果对 $10^9 + 7$ 取模”。 为什么要取模？因为答案太大了，long long 都存不下（可能有几千位），只能存它的余数。

7.3.1 模运算三大定律

在取模的世界里，加法、减法、乘法都可以先做后取模，结果不变。

1. $(a + b) \pmod m = ((a \pmod m) + (b \pmod m)) \pmod m$
2. $(a \times b) \pmod m = ((a \pmod m) \times (b \pmod m)) \pmod m$
3. 减法坑点：$(a - b) \pmod m$ C++ 中，负数取模还是负数（如 $-2 \% 5 = -2$）。但在数学上我们希望得到正余数。 正确写法：((a - b) % m + m) % m

7.3.2 快速幂 (Binary Exponentiation / Quick Pow)

场景：计算 $a^b \pmod m$。 如果 $b = 10^{18}$，你用 for 循环乘 $b$ 次，这辈子都跑不完。

思路：倍增思想。 比如算 $3^{10}$：

• 不需要乘 10 次。
• $3^{10} = (3^5)^2$
• $3^5 = 3 \times (3^2)^2$
• 只需要算 $O(\log b)$ 次。

核心代码模板 (背诵全文)： 这是算法竞赛中使用频率最高的模板之一。

typedef long long ll;
 
// 计算 (base ^ power) % mod
ll quick_pow(ll base, ll power, ll mod) {
    ll result = 1;
    while (power > 0) {
        // 如果 power 是奇数，把当前的 base 乘进结果
        if (power & 1) { 
            result = (result * base) % mod;
        }
        // base 自己平方
        base = (base * base) % mod;
        // power 除以 2
        power >>= 1; 
    }
    return result;
}

复杂度：$O(\log b)$。即便 $b=10^{18}$，也只需要计算约 60 次。

🧠 本章小结与练习

掌握了GCD、素数筛和快速幂，你就拿到了通往初级数论题的钥匙。

练习作业：

1. P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题 (洛谷)：综合考察 GCD 和 LCM。
2. P3383 【模板】线性筛素数：先试着用埃氏筛写，如果 TLE 了再去学一下欧拉筛。
3. P1226 【模板】快速幂：直接拿上面的模板去跑，感受 $O(\log N)$ 的速度。

搞定了基础数学，我们还需要搞定计算机底层的一些魔法——位运算。 为什么有的高手可以用一行代码完成你十行代码的逻辑？为什么 $2^{20}$ 可以写成 1 << 20？