本课时有配套视频讲解，购买后即可观看（永久有效）
费马小定理
一、课上练习
编程练习
二、知识总结
✨ 核心思想
费马小定理（Fermat's Little Theorem）是数论中最重要的定理之一：
若 p 是质数，且 a 不是 p 的倍数，则 a^(p-1) ≡ 1 (mod p)。
等价形式：对任意整数 a，a^p ≡ a (mod p)（无论 a 是否为 p 的倍数）。
费马小定理是模逆元（a^(-1) ≡ a^(p-2) mod p）的理论基础，也是快速幂在模运算中广泛应用的核心原因。
✨ 定理内容与证明
定理
若 p 是质数，gcd(a, p) = 1，则 a^(p-1) ≡ 1 (mod p)。
证明（利用模 p 乘法群）
考虑集合 {1, 2, 3, ..., p-1}。将每个元素乘以 a，得到 {a, 2a, 3a, ..., (p-1)a}。
关键性质：这些数模 p 后仍然是 {1, 2, ..., p-1} 的一个排列。
证明：如果 ia ≡ ja (mod p) 且 i ≠ j，则 (i-j)a ≡ 0 (mod p)。因为 gcd(a,p)=1，所以 p | (i-j)。但 1 ≤ i, j ≤ p-1，所以 |i-j| < p，矛盾。因此这 p-1 个数模 p 后两两不同。
将两组数分别乘起来：
(a)(2a)(3a)...((p-1)a) ≡ 1 × 2 × 3 × ... × (p-1) (mod p)
a^(p-1) × (p-1)! ≡ (p-1)! (mod p)因为 gcd((p-1)!, p) = 1，两边除以 (p-1)! 得：
a^(p-1) ≡ 1 (mod p)推论
a^(-1) ≡ a^(p-2) (mod p)：这是模逆元的费马小定理求法。a^n mod p = a^(n mod (p-1)) mod p（当 gcd(a,p)=1 时）：可用于降幂。
✨ 代码实现
快速幂
fast_power.cpp
1#include <bits/stdc++.h>
2using namespace std;
3
4typedef long long ll;
5
6// 快速幂：计算 a^n mod p
7// 原理：将 n 拆成二进制，利用 a^(2k) = (a^k)^2
8ll power(ll a, ll n, ll p) {
9 ll result = 1;
10 a %= p; // 先取模，防止第一次乘法溢出
11
12 while (n > 0) {
13 if (n & 1) {
14 // n 的当前最低位为 1，乘入结果
15 result = result * a % p;
16 }
17 a = a * a % p; // 底数平方
18 n >>= 1; // n 右移一位
19 }
20 return result;
21}
22
23int main() {
24 ios::sync_with_stdio(false);
25 cin.tie(nullptr);
26
27 ll a, n, p;
28 cin >> a >> n >> p;
29
30 cout << a << "^" << n << " mod " << p << " = "
31 << power(a, n, p) << "\n";
32
33 return 0;
34}费马小定理的应用：大指数降幂
fermat_power_reduction.cpp
1#include <bits/stdc++.h>
2using namespace std;
3
4typedef long long ll;
5
6ll power(ll a, ll n, ll p) {
7 ll result = 1;
8 a %= p;
9 while (n > 0) {
10 if (n & 1) result = result * a % p;
11 a = a * a % p;
12 n >>= 1;
13 }
14 return result;
15}
16
17// 计算 a^(b^c) mod p，其中 p 是质数
18// 利用费马小定理：a^(b^c) mod p = a^(b^c mod (p-1)) mod p
19ll solve(ll a, ll b, ll c, ll p) {
20 if (a % p == 0) return 0; // a 是 p 的倍数
21
22 // 先计算指数 b^c mod (p-1)
23 ll exp = power(b, c, p - 1);
24
25 // 再计算 a^exp mod p
26 return power(a, exp, p);
27}
28
29int main() {
30 ios::sync_with_stdio(false);
31 cin.tie(nullptr);
32
33 ll a, b, c, p;
34 cin >> a >> b >> c >> p;
35
36 cout << a << "^(" << b << "^" << c << ") mod " << p
37 << " = " << solve(a, b, c, p) << "\n";
38
39 return 0;
40}组合数取模（综合应用）
comb_mod.cpp
1#include <bits/stdc++.h>
2using namespace std;
3
4typedef long long ll;
5const ll MOD = 1e9 + 7;
6const int MAXN = 1000005;
7
8ll fac[MAXN]; // 阶乘
9ll inv_fac[MAXN]; // 阶乘的逆元
10
11ll power(ll a, ll n, ll p) {
12 ll result = 1;
13 a %= p;
14 while (n > 0) {
15 if (n & 1) result = result * a % p;
16 a = a * a % p;
17 n >>= 1;
18 }
19 return result;
20}
21
22// 预处理阶乘和阶乘逆元
23void init(int n) {
24 fac[0] = 1;
25 for (int i = 1; i <= n; i++) {
26 fac[i] = fac[i - 1] * i % MOD;
27 }
28
29 // 利用费马小定理求 n! 的逆元
30 inv_fac[n] = power(fac[n], MOD - 2, MOD);
31
32 // 逆向递推其余阶乘逆元
33 // inv_fac[i] = inv_fac[i+1] * (i+1) % MOD
34 for (int i = n - 1; i >= 0; i--) {
35 inv_fac[i] = inv_fac[i + 1] * (i + 1) % MOD;
36 }
37}
38
39// C(n, k) mod p
40ll comb(int n, int k) {
41 if (k < 0 || k > n) return 0;
42 return fac[n] % MOD * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
43}
44
45int main() {
46 ios::sync_with_stdio(false);
47 cin.tie(nullptr);
48
49 init(MAXN - 1);
50
51 int n, k;
52 cin >> n >> k;
53
54 cout << "C(" << n << ", " << k << ") mod " << MOD
55 << " = " << comb(n, k) << "\n";
56
57 return 0;
58}✨ 执行示例
快速幂计算 2^10 mod 1000000007
1n = 10 = 1010(二进制)
2
3步骤:
4n=10, bit=0: a=2, result=1 (不乘) → a=4
5n=5, bit=1: a=4, result=1*4=4 → a=16
6n=2, bit=0: a=16, result=4 (不乘) → a=256
7n=1, bit=1: a=256, result=4*256=1024 → a=65536
8
9结果：2^10 = 1024 ✓费马小定理降幂
计算 2^(3^100) mod 13：
1p = 13（质数），p-1 = 12
2
3第一步：计算指数 3^100 mod 12
4 3^1 mod 12 = 3
5 3^2 mod 12 = 9
6 3^3 mod 12 = 27 mod 12 = 3
7 规律：3^奇数 ≡ 3, 3^偶数 ≡ 9 (mod 12)
8 100 是偶数，所以 3^100 mod 12 = 9
9
10第二步：计算 2^9 mod 13
11 2^1 = 2
12 2^2 = 4
13 2^4 = 16 mod 13 = 3
14 2^8 = 9
15 2^9 = 2^8 * 2^1 = 9 * 2 = 18 mod 13 = 5
16
17结果：2^(3^100) mod 13 = 5✨ 解题步骤详解
- 识别费马小定理的应用场景：
- 求模逆元：
a^(-1) = a^(p-2) mod p。 - 大指数取模：通过
a^n mod p = a^(n mod (p-1)) mod p降幂。 - 组合数取模：利用阶乘逆元计算 C(n,k)。
- 求模逆元：
- 实现快速幂：这是费马小定理的计算基础。
- 预处理优化：需要多次查询组合数时，预处理阶乘和阶乘逆元。
- 注意特殊情况：当 a 是 p 的倍数时，
a^(p-1)不等于 1 而是 0。
✨ 常见错误
- 忽略 gcd(a,p)=1 的前提条件：当 a 是 p 的倍数时不能使用费马小定理降幂，结果直接为 0。
- 快速幂中 int 溢出：
a * a可能超过 int 范围，必须使用 long long。当模数接近 10^18 时，还需要用__int128或龟速乘。 - 降幂时指数取模的模数搞错：
a^n mod p中，指数 n 应对p-1取模（不是对 p 取模）。 - 阶乘逆元递推方向搞反：应先求
inv_fac[n]，然后从 n-1 递推到 0，而不是从 0 递推到 n。 - 组合数中 k > n 的情况：需要特判返回 0。
✨ 算法评价
| 指标 | 值 |
|---|---|
| 快速幂时间复杂度 | O(log n) |
| 预处理组合数 | O(n + log p) |
| 单次查询组合数 | O(1) |
| 适用条件 | 模数 p 必须是质数 |
| 竞赛出现频率 | 极高，几乎每场比赛都会用到 |
费马小定理和快速幂是算法竞赛中最基础、最常用的工具之一。掌握它们不仅能解决模逆元问题，还能高效处理组合计数、矩阵快速幂等一系列问题。可以说，不会快速幂就无法参加算法竞赛。