第7章：数论（Number Theory）

一、导读

7.1 本章学习目标

数论是数学中最古老的分支之一，研究整数的性质。在算法竞赛中，数论题目以其简洁的描述和深刻的数学内涵而著称。本章将介绍竞赛中最常用的数论知识和算法。

本章的核心学习目标包括：

掌握素数判定和筛法：试除法、埃氏筛法、线性筛法，以及它们在预处理中的应用。
精通最大公约数算法：辗转相除法（欧几里得算法）及其扩展——扩展欧几里得算法。
理解快速幂算法：O(log b) 计算 a^b mod m，这是数论题目的基础工具。
掌握模运算的性质：同余的传递性、加法/乘法性质，以及在组合数学中的应用。
理解逆元的概念和求法：费马小定理和扩展欧几里得两种方法。
学会数论问题的建模：将组合问题、计数问题转化为数论模型。

7.2 为什么本章如此重要

数论在算法竞赛中占有独特的地位。与其他专题不同，数论题目往往"入口容易、深入困难"——你很快就能理解题意，但要找到高效的解法需要扎实的数学功底。

数论算法的另一个特点是高度可复用。快速幂、GCD、素数筛、逆元这些工具，几乎在每一场竞赛中都会用到。它们不仅是独立的考点，更是解决组合数学、概率、密码学等问题的基础。

更重要的是，数论训练的是你的数学思维能力。竞赛中的数论题目要求你能够发现数字之间的规律，将复杂的计算分解为简单的步骤，利用数学性质简化问题。这种思维方式对整个计算机科学的学习都大有裨益。

7.3 核心问题引导

在阅读本章时，请带着以下问题思考：

为什么试除法判断素数只需要检查到 √n？这个结论如何证明？

埃氏筛法和线性筛法的区别是什么？线性筛法为什么是"线性"的？

辗转相除法为什么能求 GCD？它的正确性如何证明？时间复杂度是多少？

快速幂的核心思想是什么？为什么它能将 O(b) 优化到 O(log b)？

什么是模逆元？在什么条件下逆元存在？如何求？

当题目要求"答案对 10⁹+7 取模"时，除法应该如何处理？

二、核心概念详解

7.1 素数

7.1.1 素数判定——试除法

素数是大于 1 的自然数中，除了 1 和自身以外没有其他因数的数。最朴素的判定方法是试除法：

cpp

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

为什么只需要检查到 √n？ 如果 n 有一个大于 √n 的因数 d，那么 n/d 也是一个因数，且 n/d < √n。所以如果 n 不是素数，它一定有一个不超过 √n 的因数。

时间复杂度：O(√n)。对于 n ≤ 10¹²，一次判定大约需要 10⁶ 次运算，完全可以接受。

7.1.2 埃氏筛法

如果需要找出 1~n 范围内的所有素数，逐个判定效率太低。埃拉托斯特尼筛法（Eratosthenes Sieve）可以高效地完成这个任务：

cpp

const int MAXN = 1000005;
bool is_prime[MAXN];
int primes[MAXN], cnt = 0;

void sieve(int n) {
    for (int i = 2; i <= n; i++) is_prime[i] = true;
    for (int i = 2; (long long)i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
    for (int i = 2; i <= n; i++)
        if (is_prime[i]) primes[cnt++] = i;
}

核心思想：从 2 开始，每找到一个素数，就将它的所有倍数标记为合数。注意内层循环从 i*i 开始，因为比 i*i 小的倍数已经被更小的素数筛掉了。

时间复杂度：O(n log log n)，接近线性。

7.1.3 线性筛法（欧拉筛）

埃氏筛法的问题是，某些合数会被多个素数重复标记。线性筛法通过让每个合数只被它的最小素因子筛掉，实现了真正的 O(n)：

cpp

bool not_prime[MAXN];
int primes[MAXN], cnt = 0;

void linear_sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!not_prime[i]) primes[cnt++] = i;
        for (int j = 0; j < cnt && (long long)i * primes[j] <= n; j++) {
            not_prime[i * primes[j]] = true;
            if (i % primes[j] == 0) break;  // 关键：保证每个合数只被最小素因子筛掉
        }
    }
}

关键理解：if (i % primes[j] == 0) break; 这行保证了 i * primes[j] 中 primes[j] 是 i * primes[j] 的最小素因子。如果 primes[j] 整除 i，那么对于更大的素数 primes[j+1]，i * primes[j+1] 的最小素因子仍然是 primes[j]（因为 primes[j] 整除 i），应该等到 i' = i / primes[j] * primes[j+1] 时再筛。

7.2 最大公约数（GCD）

7.2.1 辗转相除法

欧几里得算法（辗转相除法）是求 GCD 的经典方法：

cpp

long long gcd(long long a, long long b) {
    return b ? gcd(b, a % b) : a;
}

正确性证明：设 a = kb + r，则 gcd(a, b) = gcd(b, r)。证明：如果 d | a 且 d | b，则 d | (a - kb) = r，所以 d | b 且 d | r。反之亦然。因此 a 和 b 的公因数集合与 b 和 r 的公因数集合相同，GCD 也相同。

时间复杂度：O(log(min(a, b)))。这是斐波那契数列的增长速度决定的——最坏情况是输入两个相邻的斐波那契数。

7.2.2 最小公倍数（LCM）

cpp

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;  // 注意先除后乘，防止溢出
}

7.2.3 扩展欧几里得算法

扩展欧几里得算法不仅求 gcd(a, b)，还求出满足 ax + by = gcd(a, b) 的整数 x, y：

cpp

long long extgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    long long d = extgcd(b, a % b, x, y);
    long long tmp = x;
    x = y;
    y = tmp - a / b * y;
    return d;
}

应用：求解线性同余方程 ax ≡ c (mod m)，即 ax + my = c。当 gcd(a, m) | c 时有解。

7.3 快速幂

7.3.1 算法原理

计算 a^b mod m，朴素方法需要 O(b) 次乘法。快速幂利用二进制分解将复杂度降到 O(log b)：

将 b 表示为二进制：b = 2^k₁ + 2^k₂ + ... + 2^kᵣ

则 a^b = a^(2^k₁) × a^(2^k₂) × ... × a^(2^kᵣ)

而 a^(2^k) 可以通过反复平方得到：a², a⁴, a⁸, ...

cpp

typedef long long ll;

ll power(ll a, ll b, ll m) {
    ll res = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) res = res * a % m;  // b 的当前位为 1，乘入结果
        a = a * a % m;                  // a 平方
        b >>= 1;                        // b 右移一位
    }
    return res;
}

示例：计算 3^13 mod 7

13 = 1101₂
res = 1, a = 3
b = 1101, 最低位为 1: res = 1 * 3 = 3, a = 9 % 7 = 2, b = 110
b = 110,  最低位为 0: a = 4, b = 11
b = 11,   最低位为 1: res = 3 * 4 = 12 % 7 = 5, a = 16 % 7 = 2, b = 1
b = 1,    最低位为 1: res = 5 * 2 = 10 % 7 = 3, a = 4, b = 0
结果：3^13 mod 7 = 3

7.3.2 快速乘

当 a, m 达到 10¹⁸ 级别时，a * a 会溢出 long long。这时需要快速乘（类似快速幂的思想）：

cpp

ll mul(ll a, ll b, ll m) {
    ll res = 0;
    a %= m;
    while (b > 0) {
        if (b & 1) res = (res + a) % m;
        a = (a + a) % m;
        b >>= 1;
    }
    return res;
}

或者使用 __int128（GCC 扩展）：

cpp

ll mul(ll a, ll b, ll m) {
    return (__int128)a * b % m;
}

7.4 模运算

7.4.1 基本性质

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a - b) mod m = ((a mod m) - (b mod m) + m) mod m  // 注意加 m 防负数
(a * b) mod m = ((a mod m) * (b mod m)) mod m

除法没有简单的模运算性质！ (a / b) mod m ≠ (a mod m) / (b mod m)。要计算 (a / b) mod m，需要求 b 的逆元。

7.4.2 逆元

b 关于 m 的逆元 b⁻¹ 满足：b × b⁻¹ ≡ 1 (mod m)

存在条件：gcd(b, m) = 1

求法一：费马小定理（当 m 为素数时）

b^(m-1) ≡ 1 (mod m) ⟹ b⁻¹ ≡ b^(m-2) (mod m)

cpp

ll inv(ll b, ll m) {
    return power(b, m - 2, m);  // 要求 m 是素数
}

求法二：扩展欧几里得

b × x ≡ 1 (mod m) ⟹ b × x + m × y = 1

cpp

ll inv(ll b, ll m) {
    ll x, y;
    ll d = extgcd(b, m, x, y);
    if (d != 1) return -1;  // 逆元不存在
    return (x % m + m) % m;
}

7.4.3 组合数取模

计算 C(n, k) mod p，其中 p 是素数：

cpp

// 预处理阶乘和阶乘的逆元
const int MAXN = 1000005;
const ll MOD = 1e9 + 7;
ll fact[MAXN], inv_fact[MAXN];

void init() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fact[i] = fact[i - 1] * i % MOD;
    inv_fact[MAXN - 1] = power(fact[MAXN - 1], MOD - 2, MOD);
    for (int i = MAXN - 2; i >= 0; i--)
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
}

ll C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] % MOD * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

三、实战案例

3.1 案例一：素数密度

问题描述：给定 L 和 R（1 ≤ L ≤ R ≤ 10¹²，R - L ≤ 10⁶），求 [L, R] 范围内有多少个素数。

cpp

#include <cstdio>
#include <cstring>
using namespace std;

typedef long long ll;

const int MAXN = 1000005;
bool small_prime[MAXN];
int primes[MAXN], cnt = 0;
bool is_prime[MAXN];

void segment_sieve(ll L, ll R) {
    // 先筛出 sqrt(R) 以内的素数
    int sq = (int)sqrt((double)R) + 1;
    for (int i = 2; i <= sq; i++) small_prime[i] = true;
    for (int i = 2; i * i <= sq; i++) {
        if (small_prime[i]) {
            for (int j = i * i; j <= sq; j += i)
                small_prime[j] = false;
        }
    }
    for (int i = 2; i <= sq; i++)
        if (small_prime[i]) primes[cnt++] = i;
    
    // 区间筛法
    for (int i = 0; i <= R - L; i++) is_prime[i] = true;
    if (L == 0) is_prime[0] = false;
    if (L <= 1 && 1 <= R) is_prime[1 - L] = false;
    
    for (int i = 0; i < cnt; i++) {
        ll p = primes[i];
        ll start = max(p * p, (L + p - 1) / p * p);
        for (ll j = start; j <= R; j += p)
            is_prime[j - L] = false;
    }
}

int main() {
    ll L, R;
    scanf("%lld%lld", &L, &R);
    segment_sieve(L, R);
    int ans = 0;
    for (int i = 0; i <= R - L; i++)
        if (is_prime[i]) ans++;
    printf("%d\n", ans);
    return 0;
}

3.2 案例二：青蛙约会（扩展欧几里得）

问题描述：两只青蛙在数轴上，分别在位置 x 和 y，每次分别跳 m 和 n 的距离。问能否在同一时间到达同一位置。

转化为方程：(m - n) × t ≡ (y - x) (mod L)，用扩展欧几里得求解。

cpp

#include <cstdio>
using namespace std;
typedef long long ll;

ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll d = extgcd(b, a % b, x, y);
    ll tmp = x; x = y; y = tmp - a / b * y;
    return d;
}

int main() {
    ll x, y, m, n, L;
    scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &L);
    
    ll a = m - n, b = L, c = y - x;
    if (a < 0) { a = -a; c = -c; }
    
    ll X, Y;
    ll d = extgcd(a, b, X, Y);
    if (c % d != 0) {
        printf("Impossible\n");
    } else {
        ll mod = b / d;
        ll ans = (X % mod * (c / d) % mod + mod) % mod;
        printf("%lld\n", ans);
    }
    return 0;
}

四、本章小结

本章系统介绍了算法竞赛中的基础数论知识：

素数：试除法 O(√n)、埃氏筛法 O(n log log n)、线性筛法 O(n)。

GCD/LCM：辗转相除法 O(log n)，扩展欧几里得求线性同余方程的解。

快速幂：O(log b) 计算 a^b mod m，是数论计算的基础工具。

模运算：加减乘的模运算性质，除法需要逆元。

逆元：费马小定理（素数模）和扩展欧几里得两种求法。

组合数取模：预处理阶乘和阶乘逆元，O(1) 查询。

数论的核心在于数学推导。竞赛中的数论题目往往需要你先用数学方法分析问题，然后才能写出高效的代码。多做题、多总结，是提升数论能力的唯一途径。

五、思考与练习

思考题

线性筛法中 if (i % primes[j] == 0) break; 的作用是什么？如果去掉这行会怎样？

扩展欧几里得算法求出的 x, y 是唯一的吗？所有解的形式是什么？

快速幂能否推广到矩阵幂？如何计算矩阵的 n 次幂？

当模数不是素数时，如何求逆元？

编程练习

素数对猜想：验证哥德巴赫猜想——对于偶数 n（4 ≤ n ≤ 10⁶），找出一对素数 p, q 使得 p + q = n。

美素数：如果一个素数的各位数字之和也是素数，称它为"美素数"。求 [L, R] 内美素数的个数。

余数问题：求满足 x ≡ a₁ (mod m₁) 且 x ≡ a₂ (mod m₂) 的最小正整数 x（中国剩余定理）。

矩阵快速幂：用矩阵快速幂计算斐波那契数列的第 n 项（对 10⁹+7 取模）。