①核心要点与万能模板
| 知识板块 | 必须记住的核心 | 复杂度 |
|---|
| 同余定义 | a ≡ b (mod m) ⟺ m | (a−b) ⟺ 存在 k 使 a = b + km | — |
| 同余运算 | 加减乘保持同余，除法必须转成乘逆元 | — |
| 负数取模 | 写成 (x % m + m) % m | O(1) |
| 快速幂 | 末位为 1 乘进答案，底数平方，指数右移 | O(log b) |
| 逆元存在性 | 存在 ⟺ gcd(a, m) = 1；模 m 下唯一 | — |
| 费马小定理法 | p 为素数时 a⁻¹ = a^(p−2) mod p | O(log p) |
| 扩展欧几里得法 | 解 a·x + m·y = 1，适用于任意模数 | O(log m) |
| 线性递推法 | inv[i] = (p − p/i) × inv[p % i] % p | O(n) |
| 分数取模 | (a/b) mod p = a × inv(b) mod p | O(log p) |
| 组合数取模 | C(n,m) = fac[n] × invFac[m] × invFac[n−m] | O(n) 预处理 + O(1) 查询 |
C++万能模板：快速幂 + exgcd + 逆元三件套
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/* ===== 1. 快速幂：a^b mod p ===== */
ll qpow(ll base, ll exp, ll p) {
ll res = 1 % p;
base %= p;
while (exp) {
if (exp & 1) res = res * base % p;
base = base * base % p;
exp >>= 1;
}
return res;
}
/* ===== 2. 扩展欧几里得：a*x + b*y = gcd(a,b) ===== */
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) { x = 1; y = 0; return a; }
ll d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
/* ===== 3. 单个逆元（通用，任意模数） ===== */
ll inv(ll a, ll m) {
ll x, y;
exgcd(a, m, x, y);
return (x % m + m) % m;
}
/* ===== 4. 单个逆元（仅 p 为素数，更短更快） ===== */
ll invPrime(ll a, ll p) { return qpow(a, p - 2, p); }
/* ===== 5. 线性求 1..n 的全部逆元 ===== */
const int MAXN = 3000005;
ll invTab[MAXN];
void buildInv(ll n, ll p) {
invTab[1] = 1;
for (int i = 2; i <= n; i++)
invTab[i] = (p - p / i) * invTab[p % i] % p;
}
🔍 代码逐段解析 · 逆元三件套万能模板
qpow(base, exp, p) —— p 作参数的通用版；res = 1 % p 兼容 p = 1，base 先取模。
exgcd —— 递归 + 回代，返回 gcd(a,b)，带回一组解；任何调用方都要检查返回值。
inv(a, m) —— 通用逆元：调 exgcd 后 (x % m + m) % m，任意模数（只要互质）都能用。
invPrime(a, p) —— 素数模专用：qpow(a, p - 2, p)，一行搞定，但前提 p 必须是素数。
buildInv(n, p) —— 线性打表：invTab[1] = 1 起步，公式 (p - p/i) * invTab[p%i] % p，O(n) 求全部逆元。
易错点 —— ① 场景混用：模数是合数时误调 invPrime；② buildInv 要求 1 ≤ i < p，n 超过 p 时公式失效。
🔑 考场三步走
① 看到"取模 + 除法" → 立即想到逆元；
② 确认模数是否素数 + 除数是否互质 → 决定用哪种求法；
③ 所有中间结果用 long long，负数结果一律 (x % m + m) % m。
②拓展案例
拓展1：等比数列求和（分治 vs 逆元公式）
问题：给定 a, n, p（p 为素数，a mod p ≠ 1），求 a + a² + a³ + … + aⁿ mod p，n ≤ 10¹⁸。
方法一：分治 无需逆元
记 S(n) = a + a² + … + aⁿ。若 n 为偶数，则前半段与后半段只差一个 a^(n/2) 因子：
S(n) = S(n/2) × (1 + a^(n/2))
若 n 为奇数，则 S(n) = S(n−1) + aⁿ。递归深度 O(log n)，每层带一次快速幂，总复杂度 O(log² n)。
方法二：逆元公式 O(log n)
由等比数列求和公式，分子分母同乘逆元：
S(n) = (a^(n+1) − a) × inv(a − 1) mod p
只需一次快速幂加一次求逆元，复杂度 O(log n)。但要求 a ≢ 1 (mod p)，否则 a − 1 无逆元，必须退回分治法。
C++等比数列求和 — 两种实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long MOD = 1000000007;
ll qpow(ll base, ll exp) {
ll res = 1; base %= MOD;
while (exp) {
if (exp & 1) res = res * base % MOD;
base = base * base % MOD; exp >>= 1;
}
return res;
}
// 方法一：分治，O(log^2 n)，不需要逆元
ll sumPow(ll a, ll n) {
if (n == 0) return 0;
if (n & 1) return (sumPow(a, n - 1) + qpow(a, n)) % MOD;
ll half = sumPow(a, n / 2);
return half * (1 + qpow(a, n / 2)) % MOD;
}
// 方法二：逆元公式，O(log n)，要求 a % MOD != 1
ll sumPowFast(ll a, ll n) {
ll num = (qpow(a, n + 1) - a % MOD + MOD) % MOD;
ll den = qpow((a - 1 + MOD) % MOD, MOD - 2);
return num * den % MOD;
}
int main() {
cout << sumPow(2, 10) << " " << sumPowFast(2, 10) << endl;
cout << sumPow(3, 1000000000000000000LL) << endl;
return 0;
}
🔍 代码逐段解析 · 等比数列求和两实现
qpow —— 标准快速幂，被两种方法共同调用。
sumPow（分治） —— n 为奇数先拆出一项 sumPow(a, n-1) + qpow(a, n)；n 为偶数用 S(n/2) * (1 + a^(n/2))。递归深度 O(log n)，每层一次快速幂，总 O(log²n)，不依赖逆元。
sumPowFast（逆元公式） —— 分子 (qpow(a, n+1) - a % MOD + MOD) % MOD：先减后补 MOD 防负数；分母 qpow((a - 1 + MOD) % MOD, MOD - 2) 用费马小定理求 inv(a−1)。
易错点 —— ① a ≡ 1 (mod p) 时 a−1 无逆元，此函数必须先特判（答案为 (n+1) mod p）；② 减法后忘记 + MOD 导致负数输出。
运行结果
2046 2046
（2 + 4 + ... + 1024 = 2046，两种方法一致 ✓）
983857628 占位
拓展2：矩阵快速幂求斐波那契第 n 项
问题：求 F(n) mod p，其中 F(1) = F(2) = 1，n ≤ 10¹⁸。
思路 快速幂的推广
把递推写成矩阵形式：
[F(n+1), F(n)]ᵀ = [[1,1],[1,0]] × [F(n), F(n−1)]ᵀ
于是 [F(n+1), F(n)] = [[1,1],[1,0]]^(n−1) × [F(2), F(1)]。矩阵乘法的"指数"同样是数，只是乘法变成了矩阵乘法 —— 快速幂的二进制分解逻辑一字不改就能复用。
复杂度：矩阵乘法常数是 2³ = 8 次标量乘法，总复杂度 O(8 · log n)。
C++矩阵快速幂 — 完整代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long MOD = 1000000007;
struct Mat {
ll m[2][2];
Mat() { memset(m, 0, sizeof(m)); }
};
Mat mul(Mat A, Mat B) {
Mat C;
for (int i = 0; i < 2; i++)
for (int k = 0; k < 2; k++) {
if (!A.m[i][k]) continue;
for (int j = 0; j < 2; j++)
C.m[i][j] = (C.m[i][j] + A.m[i][k] * B.m[k][j]) % MOD;
}
return C;
}
Mat mpow(Mat A, ll n) {
Mat R;
R.m[0][0] = R.m[1][1] = 1; // 单位阵，相当于数字里的 1
while (n) {
if (n & 1) R = mul(R, A);
A = mul(A, A);
n >>= 1;
}
return R;
}
int main() {
ll n; cin >> n;
if (n <= 2) { cout << 1 << endl; return 0; }
Mat A;
A.m[0][0] = 1; A.m[0][1] = 1;
A.m[1][0] = 1; A.m[1][1] = 0;
Mat R = mpow(A, n - 1);
cout << R.m[0][0] << endl; // 左上角即 F(n)
return 0;
}
运行结果
输入: 10
输出: 55
输入: 50
输出: 586268941
（F(50) = 12586269025，模 10^9+7 得 586268941）
输入: 1000000000000000000
输出: 209783453
（n = 10^18，只需约 60 轮矩阵乘法）
拓展3：指数有上万位怎么办 —— 十进制快速幂
问题：求 a^b mod p，其中 b 是长度可达 10⁵ 的十进制字符串。
方法一：十进制快速幂 绝对正确
把指数 b 看成十进制串，从高位到低位处理，每位做"乘 10 再补上这一位"：
res ← res¹⁰ × a^(当前数字)
例如 b = "123"：先处理 1 得 a¹；处理 2 时 (a¹)¹⁰ × a² = a¹²；处理 3 时 (a¹²)¹⁰ × a³ = a¹²³。正确性显然。
方法二：欧拉降幂 下一讲详解
由费马小定理，a^b ≡ a^(b mod (p−1)) (mod p)（当 gcd(a,p)=1）。于是只需把 b 这个巨大字符串边读边对 p−1 取模，压缩成小整数再快速幂。复杂度 O(len + log p)，比方法一更快。
C++十进制快速幂 — 完整代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long MOD = 1000000007;
// 快速幂：a^n mod MOD
ll qpow(ll a, ll n) {
ll res = 1; a %= MOD;
while (n) {
if (n & 1) res = res * a % MOD;
a = a * a % MOD; n >>= 1;
}
return res;
}
// 指数以十进制字符串给出
ll powDec(ll a, const string &b) {
ll res = 1;
for (char c : b) {
res = qpow(res, 10); // 指数"乘 10"
res = res * qpow(a, c - '0') % MOD; // 再补上这一位数字
}
return res;
}
int main() {
ll a; string b;
cin >> a >> b;
cout << powDec(a, b) << endl;
return 0;
}
🔍 代码逐段解析 · 十进制快速幂
qpow —— 标准快速幂，先 a %= MOD。
powDec 核心 —— 逐字符扫描指数串：每轮 res = qpow(res, 10) 相当于 res 的指数"乘 10"，再 res = res * qpow(a, c-'0') % MOD 补上当前数字。循环不变量：res ≡ a^(已处理前缀) (mod MOD)。
main —— a 用 ll 读入，b 用 string 读入（长度可达 10⁵，绝不能转整数）。
易错点 —— ① 用 stoll 转换超长字符串直接溢出/抛异常；② 两位处理顺序颠倒（先补数字再乘 10 就变成从低位算了）；③ qpow(res, 10) 里 res 未取模就传入（本实现 qpow 内部有 a %= MOD，安全）。
运行结果
输入: 2 1000
输出: 688423210
（验算：2^1000 mod 10^9+7 = 688423210 ✓）
输入: 3 123456789012345678901234567890
输出: 175859480
（指数 30 位，long long 装不下；字符串读入完美解决）
说明：十进制快速幂每位做 10 次平方 + 最多 4 次乘法，
指数长度 10^5 时约 3×10^6 次乘法，完全可以在 1s 内跑完。