第 8.1 章：数论基础

8.1.0 从一道题出发：余数之谜

先看一道看似不可能的题目：

🔢 题目：大数幂取模 计算 3^1000000000 mod 1000000007（即 3 的十亿次方除以 10⁹+7 的余数）。 时间限制：1 秒。

先试试你会的方法

思路 1：直接乘？ 把 3 自乘十亿次——每秒 10⁸ 次运算，也需要 10 秒。太慢。

思路 2：先算出 3^10⁹ 再取模？ 3^10⁹ 有将近 5 亿位数字，long long 只能存 19 位。根本存不下。

思路 3：边乘边取模？ result = result * 3 % p 循环十亿次——溢出问题解决了，但依然是 10⁹ 次循环，还是太慢。

这章要讲的快速幂能把十亿次乘法压缩到约 30 次。而在它背后，是一整套竞赛编程中最常用的数学工具：模运算、模逆元、GCD 与扩展欧几里得。

拆解这道题需要回答的问题

1. 「边乘边取模」为什么是合法的？→ 模运算的运算性质
2. 如何把 10⁹ 次乘法降到 30 次？→ 快速幂（二进制取幂）
3. 模意义下怎么做除法？→ 模逆元
4. 逆元什么时候存在？怎么求？→ 费马小定理 / 扩展欧几里得
5. 化简分数、检验整除性还需要什么？→ GCD / LCM 与整数技巧

本章按这条线逐一展开：

学习目标：

• 正确实现模意义下的加、减、乘，避开负数与溢出陷阱
• 手写并理解快速幂，用于 a^n mod p（n ≤ 10¹⁸）
• 用费马小定理或扩展欧几里得求模逆元，并知道何时能用哪个
• 熟练使用 GCD/LCM 与常用整数技巧

8.1.1 模运算：竞赛中的「第四则运算」

为什么需要模运算？

很多题目要求输出「答案对 10⁹+7 取模」的结果。这并非随意为之——当答案极其庞大时，它是防止整数溢出的标准手段。

举个例子：「N 个元素的排列有多少种？」答案是 N!。当 N = 20 时，N! = 2,432,902,008,176,640,000，已接近 long long 的最大值（约 9.2 × 10¹⁸）；当 N = 100 时，根本无法表示。

解决方案： 对一个素数 p（通常取 10⁹+7）取模，让所有运算在模意义下进行。

三条核心性质

这三条性质说：加、减、乘可以随时取模，结果不变。这就是「边乘边取模」合法的原因——中间结果永远小于 p，永远不会溢出。

但注意：除法不在名单里。(a / b) mod p ≠ (a mod p) / (b mod p)。模意义下的除法需要 8.1.3 节的模逆元。

负数取模陷阱

C++ 的 % 对负数的结果可能是负数：

// 解答：负数取模陷阱
#include <bits/stdc++.h>
using namespace std;

int main() {
    int a = 3, b = 5, p = 7;
    cout << (a - b) % p << "\n";           // 输出 -2，不是 5！
    cout << ((a - b) % p + p) % p << "\n"; // 输出 5 ✓
    return 0;
}

数学上 3 − 5 = −2 ≡ 5 (mod 7)，但 C++ 直接给出 −2。做减法后取模，永远补一个 +p。

溢出：模运算的头号杀手

// 解答：模运算安全模板
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1e9 + 7;  // 竞赛编程标准模数

// 安全加法
ll add_mod(ll a, ll b) {
    return (a % MOD + b % MOD) % MOD;
}

// 安全减法（加 MOD 防止负数）
ll sub_mod(ll a, ll b) {
    return ((a % MOD) - (b % MOD) + MOD) % MOD;
}

// 安全乘法
// 关键：取模后 a, b < 10^9+7，乘积 < 10^18，在 long long 范围内
ll mul_mod(ll a, ll b) {
    return a % MOD * (b % MOD) % MOD;
}

int main() {
    cout << mul_mod(1000000006, 1000000006) << "\n"; // = 1（(-1)*(-1) = 1）
    return 0;
}

两个要点：

1. 只要做乘法就用 long long。 两个 int 相乘（各约 10⁹）的乘积是 10¹⁸，int 直接溢出。
2. 为什么偏偏选 10⁹+7？ 它是素数（求逆元需要，见 8.1.3 节），且 (10⁹+7)² < 2⁶³——两个取模后的数相乘不会溢出 long long。10⁹ 就不行（不是素数）。

⚠️ 致命 Bug： 在 C++ 中，若 a < b，(a - b) % MOD 可能为负数！请始终写成 (a - b + MOD) % MOD。

8.1.2 快速幂：O(log n) 的幂运算

思想：反复平方

回到开篇的问题：计算 3^10⁹ mod p，能否远少于 10⁹ 次乘法？

关键观察：幂可以按二进制拆开。

3^10 = 3^(1010₂) = 3^8 × 3^2

只需求出 3¹, 3², 3⁴, 3⁸, ...（每次自乘即平方），再把指数二进制中为 1 的位对应的幂乘进结果。3^10⁹ 的指数有约 30 个二进制位，所以只需约 30 次平方 + 至多 30 次乘法。

计算 3^10 (指数 1010₂)：
第 1 轮：位 0 = 0 → 底数平方：3 → 9
第 2 轮：位 1 = 1 → 结果乘底数：result = 9，底数平方：9 → 81
第 3 轮：位 2 = 0 → 底数平方：81 → 6561
第 4 轮：位 3 = 1 → 结果乘底数：result = 9 × 6561 = 59049 = 3^10 ✓

完整代码

// 解答：快速幂 — O(log n) 计算 a^n mod p
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll power(ll a, ll n, ll p) {
    a %= p;                 // 先把底数压到 [0, p)
    ll result = 1;
    while (n > 0) {
        if (n & 1)          // 指数当前二进制位为 1
            result = result * a % p;
        a = a * a % p;      // 底数平方：a 依次是 a^1, a^2, a^4, a^8, ...
        n >>= 1;            // 移到下一位
    }
    return result;
}

int main() {
    cout << power(2, 10, 1000) << "\n";  // 2^10 = 1024 mod 1000 = 24
    cout << power(3, 1000000000LL, 1000000007LL) << "\n"; // 开篇问题的答案
    return 0;
}

正确性：为什么这样拆是对的？

把指数写成二进制 n = b_k·2^k + ... + b_1·2 + b_0，那么：

a^n = a^(b_k·2^k) × ... × a^(b_1·2) × a^(b_0)

第 i 轮循环时，a 恰好等于 a^(2^i)。若 b_i = 1，就把这个因子乘进 result。循环结束时，指数所有为 1 的位对应的因子都乘进去了，恰好是 a^n。中间每次乘法后立即取模，数值永远小于 p² ≈ 10¹⁸，不会溢出。

复杂度： 循环次数 = n 的二进制位数 = O(log n)。n = 10¹⁸ 也只需约 60 轮。

例题：开篇问题的解答

计算 3^1000000000 mod 1000000007。

一行代码：power(3, 1000000000, 1000000007)，约 30 次循环，瞬间出答案。对比朴素的 10⁹ 次循环，快了约 3000 万倍。

8.1.3 模逆元：模意义下的除法

问题：除法不能直接取模

模运算的加、减、乘都满足「先取模再运算等价于先运算再取模」，唯独除法不行：

(6 / 2) mod 5 = 3
(6 mod 5) / (2 mod 5) = 1 / 2 = ???  ← 整数除法直接失真

可计数公式里偏偏到处是除法（C(n,k) = n! / (k!(n−k)!)）。怎么办？

逆元的定义

b 的模逆元是一个数 b⁻¹，满足：

有了它，模意义下的除法就能转化为乘法：

a / b ≡ a × b⁻¹ (mod p)

逆元何时存在？ 当且仅当 gcd(b, p) = 1。特别地，若 p 是素数且 0 < b < p，逆元一定存在——这就是题目偏爱素数模数的原因。

方法一：费马小定理（p 是素数时）

费马小定理： 若 p 是素数且 gcd(a, p) = 1，则 a^(p−1) ≡ 1 (mod p)。

两边同除一个 a：a^(p−2) ≡ a⁻¹ (mod p)。

于是一个 power 调用就能求出逆元：

// 解答：费马小定理求逆元 — O(log p)
ll mod_inv(ll a, ll p) {
    return power(a, p - 2, p);   // 仅当 p 为素数！
}

// 模意义下的除法
ll mod_div(ll a, ll b) {
    return a % MOD * mod_inv(b, MOD) % MOD;
}

验证： p = 7，求 3⁻¹。3⁵ = 243 = 34×7 + 5 → 3⁻¹ ≡ 5 (mod 7)。检验：3 × 5 = 15 ≡ 1 (mod 7) ✓。

方法二：扩展欧几里得（任意模数）

若模数不是素数（例如 p = 10⁶ = 2⁶×5⁴），费马小定理失效，但只要 gcd(a, p) = 1，逆元仍存在。这时用扩展欧几里得算法（下一节详讲其原理）：求 x, y 使 a·x + p·y = 1，则 a·x ≡ 1 (mod p)，x 就是逆元。

// 解答：扩展欧几里得求逆元 — 任意模数
long long ext_gcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long g = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

long long mod_inv_general(long long a, long long m) {
    long long x, y;
    long long g = ext_gcd(a, m, x, y);
    if (g != 1) return -1;       // gcd(a,m) != 1，逆元不存在
    return (x % m + m) % m;      // x 可能是负数，拉回 [0, m)
}

何时能用哪个？

竞赛中 99% 的题目模数都是 10⁹+7，直接用费马小定理即可。但要养成习惯：看到不认识的模数，先想想它是不是素数。

8.1.4 GCD / LCM 与扩展欧几里得

欧几里得算法（辗转相除）

两个数的最大公因数 gcd(a, b) 是能同时整除两者的最大整数。欧几里得算法基于一个简单的事实：

gcd(a, b) = gcd(b, a mod b)      （b = 0 时 gcd(a, 0) = a）

每一步都让两数严格变小，且按斐波那契级别的速度收缩，复杂度 O(log min(a, b))：

gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6

// 解答：GCD — O(log min(a,b)))
long long my_gcd(long long a, long long b) {
    while (b != 0) {
        a %= b;
        swap(a, b);
    }
    return a;
}
// 实战中直接用 C++17 的 std::gcd(a, b)（<numeric>），或 __gcd(a, b)

LCM 与先除后乘

// 解答：LCM — 先除后乘防溢出
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;   // 先除再乘！
    // 错误写法 a * b / gcd(a, b)：a*b 可能已溢出 long long
}
// a / gcd(a,b) 一定是整数，先除不损失精度；除完后再乘 b，量级可控

扩展欧几里得：求 ax + by = gcd(a, b) 的整数解

这是一个古老而强大的结论：对任意整数 a, b，一定存在整数 x, y 使 a·x + b·y = gcd(a, b)。

它在竞赛中的头号用途就是 8.1.3 节的求逆元：取 b = p，若 gcd(a, p) = 1，则 a·x + p·y = 1，即 a·x ≡ 1 (mod p)。

递归推导：设递归底层 b = 0 时取 x = 1, y = 0（此时 a·1 + 0·0 = a = gcd）。回溯时由 gcd(a, b) = gcd(b, a mod b) 可得解的回代公式：

下层解 (x1, y1) 满足 b·x1 + (a mod b)·y1 = g
由 a mod b = a − (a/b)·b 代入整理得：
    x = y1
    y = x1 − (a/b)·y1

// 解答：扩展欧几里得 — O(log min(a,b))
// 返回 gcd(a,b)，并通过引用设置 x, y 使 a*x + b*y = gcd(a,b)
long long ext_gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long g = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

int main() {
    long long x, y;
    long long g = ext_gcd(240, 46, x, y);
    // 240x + 46y = 2，例如 x = -9, y = 47：240*(-9) + 46*47 = 2 ✓
    printf("gcd=%lld, x=%lld, y=%lld\n", g, x, y);
    return 0;
}

更一般的方程 ax + by = c： 有解当且仅当 gcd(a, b) 整除 c。有解时先求 ax + by = g 的解 (x₀, y₀)，再整体乘 c/g。

8.1.5 整数技巧：不写浮点数的那份从容

整除判定（手工验算与暴力剪枝用）

向上取整除法：ceil(a/b)

正整数场景的高频写法，整数运算天然规避浮点误差：

// 解答：向上取整除法
long long ceil_div(long long a, long long b) {
    return (a + b - 1) / b;      // 等价于 (a - 1) / b + 1（a > 0）
}
// 例：把 10 个物品每箱装 3 个，需要 ceil_div(10, 3) = 4 个箱子

安全的整数平方根

sqrtl 的浮点结果在边界上可能差 1（如 n 恰是完全平方数时返回 x−1 或 x+1），务必修正：

// 解答：整数平方根 — 最大 x 使 x*x <= n
long long isqrt(long long n) {
    long long x = sqrtl(n);            // 浮点近似
    while (x * x > n) x--;             // 偏大则减
    while ((x + 1) * (x + 1) <= n) x++; // 偏小则加
    return x;
}
// 用途：试除判素数到 isqrt(n)、枚举 n 的因子对 (d, n/d)

同理，试除判素数只需检查 2 以及 3, 5, 7, ... 到 √n 的奇数——若 n 有大于 √n 的因子，必然配着一个小于 √n 的因子。

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

📇 章末速查卡

常用模数：

⚠️ 常见错误

1. a * b % MOD 溢出： int 相乘（各约 10⁹）必溢出。只要有乘法就用 long long，写 1LL * a * b % MOD。
2. 减法出负数： (a - b) % MOD 在 C++ 中可能为负。永远写 (a - b + MOD) % MOD。
3. 对非素数模数用费马小定理： 模数不是素数时 power(a, MOD-2, MOD) 给出错误结果。看到非标准模数，先判断素数性，必要时改用 ext_gcd。
4. LCM 先乘后除： a * b / gcd(a,b) 中 a*b 可能溢出。先除后乘：a / gcd(a,b) * b。
5. 逆元不存在时硬算： gcd(b, p) ≠ 1 时 b 无逆元（如 p = 4, b = 2）。此时需改写公式（约去公因子）避开除法。
6. 模数 ≥ 2×10⁹ 时乘法溢出： 若 p 接近 10¹⁸，a * a % p 本身就溢出 long long。用 __int128 做中间乘法：(__int128)a * b % p。

📋 章节小结

下一章： 第 8.2 章：素数筛法与积性函数——批量判素数、质因数分解与欧拉 φ。

🏋️ 练习题

🟢 简单

8.1-E1. 大数幂取模
给定 a, n, p，计算 a^n mod p。
数据规模： 1 ≤ a ≤ 10⁹，1 ≤ n ≤ 10¹⁸，2 ≤ p ≤ 10⁹。

8.1-E2. 最简分数
给定 N 对分数 aᵢ/bᵢ，将每个分数约分成最简形式 p/q 后输出。
数据规模： 1 ≤ N ≤ 10⁵，1 ≤ aᵢ, bᵢ ≤ 10⁹。

🟡 中等

8.1-M1. 模意义除法
给定 a, b 和素数 p，计算 (a / b) mod p（保证 p 不整除 b）。
数据规模： 1 ≤ a, b ≤ 10¹⁸，2 ≤ p ≤ 10⁹ + 7（p 为素数）。

🔴 困难

8.1-H1. 巨大模数下的幂 (USACO Platinum 风格)
给定 a, n, p，计算 a^n mod p。
数据规模： 1 ≤ a ≤ 10¹⁸，1 ≤ n ≤ 10¹⁸，2 ≤ p ≤ 10¹⁸。

第 8.1 章结束 — 下一章：素数筛法与积性函数