扩展欧拉定理：数论中的降幂利器
在算法竞赛与密码学研究中，扩展欧拉定理是解决大指数模运算问题的核心工具。 它突破了传统欧拉定理对底数互质的限制，为处理 a^b mod c 中 gcd(a, c) ≠ 1 的情况提供了完美的解决方案。
⚡ 扩展欧拉定理的核心定义
许多初学者容易混淆欧拉定理与扩展欧拉定理。标准欧拉定理要求底数 a 与模数 m 互质（即 gcd(a, m) = 1），但在实际计算中，这一条件往往无法满足。
扩展欧拉定理（Generalized Euler's Theorem）去除了互质限制，其公式如下：
a^b ≡ a^{b % φ(m) + φ(m)} (mod m)
其中，φ(m) 是欧拉函数，表示小于等于 m 且与 m 互质的正整数个数。
? 关键条件：b ≥ φ(m)
这是扩展欧拉定理生效的前置条件。如果 b < φ(m)，则直接使用普通模运算，或者套用公式时需注意指数部分不应进行取模简化，而是直接计算。但在编程实现中，为了统一处理，通常会将指数部分设为 b % φ(m) + φ(m)，并保证计算出的指数足够大以覆盖原指数。
? 适用范围
适用于所有整数 a, m ≥ 1 以及非负整数 b。无论 a 和 m 是否互质，只要指数足够大，该公式均成立。
? 与费马小定理的关系
当 m 为质数时，φ(m) = m - 1。此时扩展欧拉定理退化为费马小定理的形式：a^{m-1} ≡ 1 (mod m)（当 gcd(a,m)=1）。因此，费马小定理是扩展欧拉定理的特例。
⚙️ 定理推导与逻辑解析
理解证明过程有助于在编程中避免边界错误。扩展欧拉定理的证明基于数论中的中国剩余定理和质因数分解思想。
证明思路概要
设 m = p_1^{e_1} p_2^{e_2} ... p_k^{e_k} 为 m 的标准分解式。根据中国剩余定理，只需证明对于 m 的每个质因子幂 p_i^{e_i}，同余式均成立。
步骤 1：分解模数
将模数 m 分解为质因子的幂次乘积。由于 φ(m) 是积性函数，φ(m) 可以被分解为各质因子幂次对应欧拉值的乘积。
步骤 2：处理互质情况
如果 gcd(a, p_i^{e_i}) = 1，则直接应用标准欧拉定理：a^{φ(p_i^{e_i})} ≡ 1 (mod p_i^{e_i})。此时指数取模 φ(m) 是自然的。
步骤 3：处理不互质情况
如果 gcd(a, p_i^{e_i}) ≠ 1，说明 p_i 整除 a。当指数 b 足够大（b ≥ e_i）时，a^b 将包含因子 p_i^{e_i}，因此 a^b ≡ 0 (mod p_i^{e_i})。
步骤 4：统一指数形式
由于 φ(p_i^{e_i}) 通常大于 e_i，当 b ≥ φ(m) 时，必然有 b ≥ e_i。因此，对于不互质的质因子幂，a^{b} ≡ 0 ≡ a^{b % φ(m) + φ(m)} (mod p_i^{e_i}) 成立（因为右侧指数也足够大，结果仍为0）。
? 直观理解
可以将模运算看作是在一个环形轨道上跑步。当 a 和 m 互质时，跑步具有严格的周期性，周期为 φ(m)。当不互质时，前期可能存在一个“非周期”的过渡阶段（前缀），一旦步数超过某个阈值（即 φ(m)），就会进入一个稳定的循环状态，循环长度依然与 φ(m) 相关。扩展欧拉定理中的 + φ(m) 正是为了覆盖这个非周期前缀。
? 算法应用：大指数降幂
在编程竞赛（如ACM/ICPC、LeetCode Hard）中，经常遇到计算 a^b mod c 的问题，其中 b 可能是一个巨大的数（例如以字符串形式给出，长度超过1000位）。此时，直接计算 b 会溢出，必须使用降幂公式。
应用场景示例
| 场景 | 输入特征 | 挑战 | 解决方案 |
|---|---|---|---|
| 超级幂运算 | b 为字符串 | 无法转为 long long | 读取字符串模拟大数取模 φ(c) |
| 递归幂塔 | a^{a^{...}} | 指数爆炸 | 递归计算欧拉函数链，直到模数为1 |
| 密码学解密 | 大数模幂 | 效率低下 | 快速幂算法 + 扩展欧拉定理优化指数 |
计算步骤详解
- 计算欧拉函数：首先计算模数 c 的欧拉函数值 φ(c)。
- 处理大指数：如果指数 b 是字符串，需要将其对 φ(c) 取模。注意，如果取模后的结果小于原指数（即原指数 < φ(c)），则需要保留原值或加上 φ(c) 以保证公式适用性。通常实现为：new_b = (b % φ(c) + φ(c)) % φ(c) 这种逻辑需要谨慎，更稳妥的是：if (b >= φ(c)) new_b = b % φ(c) + φ(c); else new_b = b;。
- 快速幂计算：使用快速幂算法计算 a^{new_b} mod c。
? C++ 代码实现指南
以下是完整的 C++ 实现，包含欧拉函数计算、大数取模和快速幂三个核心模块。
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
// 1. 快速幂算法：计算 (base^exp) % mod
ll quick_pow(ll base, ll exp, ll mod) {
ll result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) {
result = (result base) % mod;
}
base = (base base) % mod;
exp >>= 1;
}
return result;
}
// 2. 计算欧拉函数 phi(n)
ll get_phi(ll n) {
ll result = n;
for (ll i = 2; i i <= n; i++) {
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
}
if (n > 1)
result -= result / n;
return result;
}
// 3. 大数字符串对 m 取模
ll string_mod(string num, ll m) {
ll res = 0;
for (char c : num) {
res = (res 10 + (c - '0')) % m;
}
return res;
}
// 4. 扩展欧拉定理主函数：计算 a^b % c
// b 以字符串形式传入
ll extended_euler(string b_str, ll a, ll c) {
ll phi_c = get_phi(c);
// 判断 b 是否大于等于 phi(c)
// 简单判断：如果字符串长度大于 phi(c) 的位数，或者长度相等但数值更大
bool b_ge_phi = false;
if (b_str.length() > to_string(phi_c).length()) {
b_ge_phi = true;
} else if (b_str.length() == to_string(phi_c).length()) {
if (b_str >= to_string(phi_c)) {
b_ge_phi = true;
}
}
ll exponent;
if (b_ge_phi) {
// 如果 b >= phi(c)，使用降幂公式：b % phi(c) + phi(c)
ll b_mod = string_mod(b_str, phi_c);
exponent = b_mod + phi_c;
} else {
// 如果 b < phi(c)，直接转换
exponent = stoll(b_str);
}
return quick_pow(a, exponent, c);
}
int main() {
string b = "100000000000000000000"; // 大指数
ll a = 2;
ll c = 1000000007;
cout << "Result: " << extended_euler(b, a, c) << endl;
return 0;
}
欧拉函数计算逻辑
欧拉函数 φ(n) 的计算基于质因数分解。公式为：φ(n) = n Π (1 - 1/p)，其中 p 是 n 的质因子。
代码中通过遍历 2 到 √n 的整数，找出所有质因子，并应用上述公式进行累乘。时间复杂度为 O(√n)，对于 n ≤ 10^9 的数据范围完全足够。
关键注意事项
- 类型溢出：在快速幂中，base base 可能溢出 long long。如果模数 mod > 10^9，需要使用快速乘（类似于快速幂的加法版本）或 __int128。
- 边界情况：当 c = 1 时，结果恒为 0。代码中需提前处理。
- 大数比较：判断 b ≥ φ(c) 时，直接比较字符串和数字的大小是容易出错的地方，务必使用字符串长度和字典序进行比较。
❓ 常见问题解答 (FAQ)
严格来说，公式 a^b ≡ a^{b % φ(m) + φ(m)} (mod m) 的推导基于 b ≥ φ(m) 的条件。如果 b < φ(m)，直接计算 a^b mod m 即可。如果在代码中强行套用公式，由于 b % φ(m) = b，公式变为 a^{b + φ(m)}，这与原式 a^b 不一定相等（除非 a^φ(m) ≡ 1，即互质情况）。因此，编程时必须先判断 b 与 φ(m) 的大小关系。
加 φ(m) 是为了确保指数始终大于等于 φ(m)，从而满足定理的使用条件。即使原指数 b 很大，取模后可能变小，加上 φ(m) 后能保证指数进入“循环区”，使得同余关系成立。这相当于在指数上增加了一个完整的周期，不影响模 m 的结果。
标准的扩展欧拉定理主要针对非负整数指数。如果指数为负，通常需要先求底数的模逆元，将负指数转化为正指数处理。此时需确保底数与模数互质，否则模逆元不存在。
如果 m 是质数，那么小于 m 且与 m 互质的正整数有 m-1 个（即 1 到 m-1）。因此，φ(m) = m - 1。