①核心要点与万能模板
| 知识板块 | 必须记住的核心 | 前提条件 |
|---|
| 费马小定理（形式一） | a^(p−1) ≡ 1 (mod p) | p 素数 且 gcd(a,p)=1 |
| 费马小定理（形式二） | a^p ≡ a (mod p) | 仅要求 p 素数 |
| 求逆元 | inv(a) ≡ a^(p−2) (mod p) | 同上 |
| 降幂 | a^k ≡ a^(k mod (p−1)) (mod p) | 同上 |
| 证明直觉 | 乘 a 后完全剩余系被重排，乘积不变 | — |
| 威尔逊定理 | (p−1)! ≡ −1 (mod p) ⟺ p 为素数 | p ≥ 2 |
| 威尔逊推论 | (p−2)! ≡ 1 (mod p) | p 为素数 |
| 威尔逊的局限 | 阶乘 O(p)，只能小范围用 | — |
| 与欧拉定理 | φ(p) = p − 1，费马是欧拉的特例 | — |
| 卢卡斯定理 | C(n,m) ≡ ∏ C(nᵢ, mᵢ) (mod p) | p 为素数，n 可极大 |
C++万能模板：费马逆元 + 降幂 + 威尔逊判定
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/* ===== 快速幂 ===== */
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;
}
/* ===== 费马小定理求逆元（p 必须是素数，且 gcd(a,p)=1） ===== */
ll invFermat(ll a, ll p) { return qpow(a, p - 2, p); }
/* ===== 降幂：指数为字符串，对 p-1 取模 ===== */
ll reduceExp(const string &k, ll p) {
ll r = 0;
for (char c : k) r = (r * 10 + (c - '0')) % (p - 1);
return r;
}
/* ===== 威尔逊定理判定（仅适合小 n，O(n)） ===== */
bool wilsonPrime(ll n) {
if (n < 2) return false;
ll fact = 1 % n;
for (ll i = 1; i <= n - 1; i++) fact = fact * i % n;
return fact == n - 1;
}
/* ===== (p-2)! mod p = 1（威尔逊推论） ===== */
ll factPMinus2(ll p) { return 1 % p; }
int main() {
cout << invFermat(3, 11) << endl; // 4
cout << qpow(2, reduceExp("1000000", 13), 13) << endl; // 3
cout << wilsonPrime(13) << " " << wilsonPrime(15) << endl; // 1 0
cout << factPMinus2(13) << endl; // 1
return 0;
}
🔍 代码逐段解析 · 万能模板四件套
qpow(base, exp, p) —— 三参快速幂，res = 1 % p、base %= p 双保险。
invFermat(a, p) —— 一行 qpow(a, p-2, p)，调用前必须自查"p 素数 + 互质"。
reduceExp(k, p) —— 字符串指数降幂：逐字符 (r*10 + digit) % (p-1)，返回压缩后的小指数。
wilsonPrime(n) —— O(n) 阶乘判定，只适合小 n；1 % n 处理退化输入。
factPMinus2(p) —— 威尔逊推论的直接实现：(p−2)! ≡ 1，所以直接返回 1 % p。
main 演示 —— invFermat(3,11)=4；qpow(2, reduceExp("1000000",13), 13)=3；wilsonPrime(13)=1、wilsonPrime(15)=0。
易错点 —— ① reduceExp 模写成 p；② 用 wilsonPrime 判大数（TLE）。
🔑 考场三步走
① 模数是素数吗？是 → 费马可用；不是 → 换欧拉定理或 exgcd；
② 指数超大吗？大 → 先对 p − 1 取模降幂；
③ 见到 (p−1)! 或 (p−2)!？→ 立刻联想威尔逊定理的 −1 与 1。
②拓展案例
拓展1：求元素的阶（幂的循环长度）
问题：给定素数 p 与 gcd(a, p) = 1，求最小的正整数 k 使 a^k ≡ 1 (mod p)。
思路 费马推论
由费马小定理，这样的 k 一定存在且 k 整除 p − 1。证明：设 k 是最小的正周期，把 p − 1 除以 k 得 p − 1 = qk + r（0 ≤ r < k），则 a^r = a^(p−1) × (a^k)^(−q) ≡ 1，若 r > 0 就与 k 的最小性矛盾，故 r = 0。
因此只需枚举 p − 1 的所有约数，从小到大检查 a^d ≡ 1 是否成立，第一个成立的 d 就是答案。因子个数约为 O(√p) 级别。
C++求元素的阶 — 完整代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qpow(ll b, ll e, ll p) {
ll r = 1 % p; b %= p;
while (e) { if (e & 1) r = r * b % p; b = b * b % p; e >>= 1; }
return r;
}
int main() {
ll a, p; cin >> a >> p;
vector<ll> divs;
for (ll d = 1; d * d <= p - 1; d++)
if ((p - 1) % d == 0) {
divs.push_back(d);
if (d != (p - 1) / d) divs.push_back((p - 1) / d);
}
sort(divs.begin(), divs.end());
for (ll d : divs)
if (qpow(a, d, p) == 1) { cout << d << endl; break; }
return 0;
}
运行结果
输入: 3 7
输出: 6
（3 的幂序列 3,2,6,4,5,1，循环长度 6，恰好等于 p-1）
输入: 2 7
输出: 3
（2 的幂序列 2,4,1,2,4,1… 周期为 3，是 p-1=6 的真因子）
输入: 10 13
输出: 6
（10 ≡ -3，(-3)^6 = 729 ≡ 1 (mod 13)，周期 6 是 12 的因子）
拓展2：从费马到 Miller-Rabin 素性测试
问题：威尔逊定理判素数太慢，有没有 O(log³n) 的替代方案？
费马素性测试 不充分
任取底数 a，若 n 是素数必有 a^(n−1) ≡ 1 (mod n)。但反过来不成立 —— 存在合数 n 使所有与它互质的 a 都满足这条式子，称为 Carmichael 数（最小的是 561 = 3 × 11 × 17）。所以费马测试只能"证伪"，不能"证实"。
Miller-Rabin 工程标准
把 n − 1 写成 2^s × d（d 为奇数）。若 n 是素数，则对任意 a，要么 a^d ≡ 1，要么存在某个 r ∈ [0, s−1] 使 a^(2^r·d) ≡ −1。这不是必要条件（合数也可能通过），但通过的合数比例极低。取 2、3、5、7、11 等几个底数，在 64 位范围内可以做到确定正确。
C++Miller-Rabin 素性测试 — 完整代码
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef __int128 lll;
// 防溢出的快速幂（模数可达 10^18，需要用 __int128 中转）
ull qpow(ull b, ull e, ull p) {
ull r = 1 % p; b %= p;
while (e) {
if (e & 1) r = (lll)r * b % p;
b = (lll)b * b % p;
e >>= 1;
}
return r;
}
bool isPrime(ull n) {
if (n < 2) return false;
for (ull p : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL})
if (n % p == 0) return n == p;
ull d = n - 1, s = 0;
while (!(d & 1)) { d >>= 1; s++; }
for (ull a : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL}) {
if (a % n == 0) continue;
ull x = qpow(a, d, n);
if (x == 1 || x == n - 1) continue;
bool ok = false;
for (ull r = 1; r < s; r++) {
x = (lll)x * x % n;
if (x == n - 1) { ok = true; break; }
}
if (!ok) return false;
}
return true;
}
int main() {
for (ull n : {561ULL, 1105ULL, 1000000007ULL, 1000000009ULL})
cout << n << " -> " << (isPrime(n) ? "Prime" : "Composite") << endl;
return 0;
}
🔍 代码逐段解析 · Miller-Rabin
qpow(ull, ull, ull) —— 模数可达 10¹⁸，两个 ull 相乘会溢出，所以用 (lll)r * b % p 走 __int128 中转。
小素数试除 —— 先用 2..37 的小素数试除并处理相等情形，挡掉大量小合数。
分解 n−1 = 2^s × d —— while (!(d & 1)) { d >>= 1; s++; } 把 2 的幂全部抽走，d 留成奇数。
主循环 —— 对每个底数 a：算 x = qpow(a, d, n)；x 为 1 或 n−1 直接通过；否则平方至多 s−1 次，途中出现 n−1 则通过，都没出现判定为合数。
main —— 测试 561、1105（Carmichael 数，费马测试抓不住、MR 能抓住）与 10⁹+7、10⁹+9（真素数）。
易错点 —— ① 忘用 __int128 导致 10¹⁸ 级模乘溢出；② s−1 的循环上界写错；③ 底数 a ≥ n 时没跳过。
运行结果
561 -> Composite
（Carmichael 数！它满足 a^560 ≡ 1 (mod 561) 对所有 gcd(a,561)=1 成立，
但 Miller-Rabin 的二次探测把它逮住了）
1105 -> Composite
（另一个 Carmichael 数）
1000000007 -> Prime
1000000009 -> Prime
（两个常用的竞赛大素数，各只需 12 次底数测试，耗时不到 1ms）
拓展3：用威尔逊定理算 (p−k)! mod p
问题：给定素数 p 与小整数 k（k < p），求 (p−k)! mod p。
思路 威尔逊 + 费马
把 (p−1)! 从高位往低位拆：(p−1)! = (p−1)(p−2)⋯(p−k) × (p−k−1)!。
模 p 下 (p−i) ≡ −i，所以前半部分等于 (−1)^k · k!。于是
(−1)^k · k! · (p−k−1)! ≡ −1 (mod p)
两边乘 (−1)^k · inv(k!)，得到
(p−k−1)! ≡ (−1)^(k+1) · inv(k!) (mod p)
特例检验：k = 1 时 (p−2)! ≡ (−1)² · inv(1) = 1，与推论吻合；k = 2 时 (p−3)! ≡ (−1)³ · inv(2) = −inv(2)。
C++用威尔逊定理计算 (p−k−1)! — 完整代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qpow(ll b, ll e, ll p) {
ll r = 1 % p; b %= p;
while (e) { if (e & 1) r = r * b % p; b = b * b % p; e >>= 1; }
return r;
}
// 用威尔逊定理推出：(p-k-1)! ≡ (-1)^(k+1) * inv(k!) (mod p)
ll factFromWilson(ll p, ll k) {
ll fk = 1 % p;
for (ll i = 1; i <= k; i++) fk = fk * i % p; // k!
ll res = qpow(fk, p - 2, p); // inv(k!)
if ((k + 1) % 2) res = (p - res) % p; // (-1)^(k+1) 为负时取反
return res;
}
// 暴力对照：直接算 (p-k-1)!（仅适合小 p）
ll brute(ll p, ll k) {
ll f = 1 % p;
for (ll i = 1; i <= p - k - 1; i++) f = f * i % p;
return f;
}
int main() {
for (ll p : {7LL, 11LL, 13LL})
for (ll k = 1; k <= 3; k++)
printf("p=%2lld k=%lld : 公式 %2lld 暴力 %2lld %s\n", p, k,
factFromWilson(p, k), brute(p, k),
factFromWilson(p, k) == brute(p, k) ? "✓" : "✗");
return 0;
}
运行结果
p= 7 k=1 : 公式 1 暴力 1 ✓
p= 7 k=2 : 公式 3 暴力 3 ✓
p= 7 k=3 : 公式 6 暴力 6 ✓
p=11 k=1 : 公式 1 暴力 1 ✓
p=11 k=2 : 公式 5 暴力 5 ✓
p=11 k=3 : 公式 2 暴力 2 ✓
p=13 k=1 : 公式 1 暴力 1 ✓
p=13 k=2 : 公式 6 暴力 6 ✓
p=13 k=3 : 公式 11 暴力 11 ✓
手工验算（p = 7）：
k=1 → (p-k-1)! = 5! = 120 ≡ 1 (mod 7)，公式 (-1)^2 · inv(1!) = 1 ✓
k=2 → (p-k-1)! = 4! = 24 ≡ 3 (mod 7)，公式 (-1)^3 · inv(2!) = -4 ≡ 3 ✓
k=3 → (p-k-1)! = 3! = 6 ≡ 6 (mod 7)，公式 (-1)^4 · inv(6) = 6 ✓
注意：暴力法需要 O(p) 次乘法，p 达 10^9 时不可行；
公式法只用 O(k + log p) 就能算出结果，这正是威尔逊定理的威力。
💡 拓展3 的关键：把下标写清楚
用同样的拆法还能得到另一条式子：把 (p−1)! 拆成"前 k−1 个因子"与 (p−k)! 的乘积，可得
(p−k)! ≡ (−1)^k · inv((k−1)!) (mod p)
两条式子只差一个因子 k，非常容易混。做题时先写清楚"乘到哪一项为止"，再代入 k 的一个具体值验证（例如 p = 7, k = 1 时答案必须是 1），确认无误后再写代码。
这类由威尔逊定理派生的阶乘化简式，在初赛填空题和部分提高组数论题中经常出现，属于"知道就能秒杀、不知道就无从下手"的知识点。