1. 项目概述：从“欧拉”家族算法说起
如果你在刷算法题或者研究密码学、数论相关的代码时，碰到“欧拉快速幂”、“欧几里得扩展算法”和“欧拉-费马降幂”这几个名词，可能会有点懵。它们名字里都带“欧拉”或“欧几里得”，听起来像是一家人，但具体是干什么的，彼此之间又有什么关系？今天，我就以一个过来人的身份，把这几个在算法竞赛和工程实践中高频出现的“硬骨头”拆开揉碎了讲清楚。这不仅仅是几个孤立的算法，它们背后串联起的是一套处理大数运算、模运算和求解方程的核心数论工具链。无论是解决“a的b次方对m取模”这种基础问题，还是应对RSA加密解密中的密钥计算，甚至是某些动态规划的状态转移优化，都离不开它们。搞懂这一套，你的算法工具箱会立刻充实不少。
简单来说，你可以这样理解它们的角色分工：
- 欧拉快速幂：解决“算得快”的问题。当指数b巨大时（比如b=10^18），如何快速计算 a^b mod m。
- 欧几里得扩展算法：解决“找关系”的问题。给定a, m，如何找到整数x, y使得 ax + my = gcd(a, m)，这在求解模线性方程（同余方程）和计算模逆元时至关重要。
- 欧拉-费马降幂：解决“指数太大”的问题。当指数b本身也是一个巨大的数，甚至可能超过任何基本类型的表示范围时，如何利用欧拉定理或费马小定理，将庞大的指数b化简到一个可控的范围，然后再用快速幂去计算。
这三个算法环环相扣，共同构成了处理模幂运算和相关数论问题的完整解决方案。接下来，我会逐一深入它们的原理、实现细节，并分享我在实际编码和解题中踩过的坑和总结的技巧。
2. 核心算法原理与思路拆解
2.1 欧拉快速幂：分而治之的指数征服术
快速幂的核心思想是二分与倍增。普通计算 a^b 需要连乘 b 次，时间复杂度是 O(b)。当 b 很大时，这是不可接受的。快速幂将指数 b 用二进制表示，利用 a^(2^k) 可以通过连续平方快速得到这一性质，将计算次数降到 O(log b)。
为什么二进制分解如此有效？假设我们要计算 3^13。13的二进制是 1101，即 13 = 8 + 4 + 0 + 1 = 2^3 + 2^2 + 2^0。 那么 3^13 = 3^(8+4+1) = 3^8 * 3^4 * 3^1。 关键在于，3^1 我们知道，3^2 = (3^1)^2，3^4 = (3^2)^2，3^8 = (3^4)^2。我们只需要通过不断平方，就能以对数级的速度得到所有 3^(2^k) 的值，然后根据b的二进制位，决定是否将对应的部分乘入结果。
与模运算的结合：在模运算背景下，我们计算的是 a^b mod m。快速幂的每一步乘法后都立即取模，利用了模运算的性质：(a * b) mod m = [(a mod m) * (b mod m)] mod m。这保证了中间结果不会溢出（在合理选择数据类型的前提下），并且最终结果正确。
注意：这里说的“欧拉快速幂”通常就是指结合了模运算的快速幂算法。虽然欧拉本人可能没直接叫这个名，但因为它常与欧拉定理等一同使用，且在数论背景下至关重要，所以常被冠以“欧拉”之名。
2.2 扩展欧几里得算法：裴蜀定理的构造性证明
普通的欧几里得算法（辗转相除法）用于求两个整数的最大公约数（gcd）。扩展欧几里得算法（Extended Euclidean Algorithm, EXGCD）则在求出 gcd(a, b) 的同时，找到一对整数 x, y，满足裴蜀等式：ax + by = gcd(a, b)。
它为什么能工作？算法基于递归。我们知道 gcd(a, b) = gcd(b, a mod b)。假设我们已经递归求解了子问题：对于 b 和 a mod b，我们找到了 x1, y1 使得 b*x1 + (a mod b)*y1 = gcd(b, a mod b) = gcd(a, b)。
现在我们需要用 a, b 表示这个等式。注意到 a mod b = a - ⌊a/b⌋ * b。代入上式： gcd(a, b) = bx1 + (a - ⌊a/b⌋ * b) * y1 = ay1 + b*(x1 - ⌊a/b⌋ * y1) 于是，对于原问题 (a, b)，我们得到了解：x = y1, y = x1 - ⌊a/b⌋ * y1。
递归基是当 b=0 时，gcd(a,0)=a，此时等式为 a1 + 00 = a，解为 x=1, y=0。
核心应用：求解模逆元在模 m 的世界里，a 的逆元 a^{-1} 定义为满足 a * a^{-1} ≡ 1 (mod m) 的整数。这等价于寻找 x 使得 ax + my = 1。这正是裴蜀等式的形式！当且仅当 gcd(a, m) = 1 时，a 在模 m 下有逆元。此时，用EXGCD解出的 x 就是 a 模 m 的逆元（可能需要调整到 0~m-1 范围内）。
2.3 欧拉-费马降幂：当指数“爆炸”时的救命稻草
快速幂解决了指数b大的问题，但如果指数b本身大得离谱呢？比如 b 是一个有1000位的整数（常见于密码学场景），你甚至无法将它读入到一个标准整数类型中。这时就需要降幂。
理论基石：欧拉定理与费马小定理
- 费马小定理：若 p 是质数，且 a 不是 p 的倍数，则 a^(p-1) ≡ 1 (mod p)。它是欧拉定理的特殊情况。
- 欧拉定理：若 a 与 m互质（即 gcd(a, m) = 1），则 a^φ(m) ≡ 1 (mod m)。其中 φ(m) 是欧拉函数，表示小于 m 且与 m 互质的正整数的个数。
降幂的核心思想：根据欧拉定理，当 a 与 m 互质时，a 的幂次对模 m 的结果，每 φ(m) 个周期会“归1”。因此，对于计算 a^b mod m，我们并不需要原始的、巨大的指数 b，而只需要知道 b 除以 φ(m) 的余数 r 即可。因为： a^b ≡ a^(k*φ(m) + r) ≡ (a^φ(m))^k * a^r ≡ 1^k * a^r ≡ a^r (mod m) 这里 b = k * φ(m) + r，0 ≤ r < φ(m)。
这样，我们就把一个天文数字般的指数 b，降低到了小于 φ(m) 的余数 r。而 φ(m) 通常远小于 b（尽管对于大的 m，φ(m) 也可能不小，但至少是可存储、可计算的）。接下来再用快速幂计算 a^r mod m 就可行了。
更一般的情况（欧拉降幂公式）：当 a 与 m不互质时，情况更复杂，但有一个更强大的降幂公式（通常称为广义欧拉降幂）： 对于计算 a^b mod m，
- 如果 b < φ(m)，直接计算 a^b mod m。
- 如果 b ≥ φ(m)，则计算 a^(b mod φ(m) + φ(m)) mod m。
这个公式在算法竞赛中处理“指数塔”类问题时非常有用，例如计算 a^(b^(c^(...))) mod m。
3. 核心细节解析与实操要点
3.1 欧拉快速幂的实现细节与边界处理
快速幂的迭代实现非常简洁，但魔鬼在细节中。
基础迭代模板（C++风格）：
long long fastPow(long long a, long long b, long long m) { long long res = 1 % m; // 注意：应对 m=1 的情况，结果应为0 a %= m; // 先取模，防止初始a过大导致后续乘法溢出 while (b > 0) { if (b & 1) { // 判断二进制最低位是否为1 res = (res * a) % m; } a = (a * a) % m; // 平方 b >>= 1; // 右移一位 } return res; }关键细节与避坑指南：
- 初始化 res = 1 % m：这是很多人忽略的一点。当模数 m=1 时，任何数模1都是0。如果写成
res = 1，那么对于 m=1，最终会返回1，这是错误的。1 % m正确处理了所有情况。 - 先对底数 a 取模：在循环开始前执行
a %= m。因为输入 a 可能很大，直接参与第一次平方a*a就可能导致溢出（即使使用long long）。提前取模不影响结果，但能保证中间计算在数据类型的表示范围内。 - 使用 long long 与溢出防范：即使 a 和 m 都在 int 范围内，
a * a也可能超出 int 范围。因此参数和中间变量通常使用long long。在极端情况下（如 m 接近 10^18），连long long乘法也会溢出，此时需要使用快速乘（类似快速幂思想的乘法）或编译器提供的__int128类型。 - 循环条件
while (b > 0)：对于非负指数 b 是标准的。如果 b 可能为 0，上述代码也正确（会直接返回 1 % m）。如果 b 可能为负数，则快速幂求模逆元，这通常需要结合扩展欧几里得算法先求逆元，将问题转化为正指数。
时间复杂度：O(log b)，空间复杂度 O(1)。这是处理模幂运算的标配。
3.2 扩展欧几里得算法的递归与迭代实现
递归实现（最直观）：
// 函数返回 gcd(a, b)，并通过引用返回 x, y long long exgcd(long long a, long long b, long long &x, long long &y) { if (b == 0) { x = 1; y = 0; return a; } long long d = exgcd(b, a % b, y, x); // 注意这里交换了x, y的位置 y -= (a / b) * x; return d; }递归实现的巧妙之处在于exgcd(b, a % b, y, x)这一句。我们递归求解的是 (b, a%b) 对应的系数 (y1, x1)。根据之前的推导，当前层的解 x = y1, y = x1 - (a/b)*y1。由于递归调用时我们传入了y和x作为下一层的“x1”和“y1”，返回后，x实际上已经存储了下一层的 y1（即当前层需要的x），y存储了下一层的 x1。所以我们只需要修正y：y = y - (a/b) * x。
迭代实现（避免递归栈溢出）：迭代版本稍复杂，但理解了原理也能写出来。它维护两组系数 (x1, y1) 和 (x2, y2)，分别对应连续两个状态。
long long exgcd_iter(long long a, long long b, long long &x, long long &y) { x = 1, y = 0; // 初始状态对应 a*1 + b*0 = a long long x1 = 0, y1 = 1; // 对应 a*0 + b*1 = b while (b != 0) { long long q = a / b; // 更新 (a, b) 为 (b, a % b) long long tmp = b; b = a % b; a = tmp; // 更新系数 long long tmp_x = x1; long long tmp_y = y1; x1 = x - q * x1; y1 = y - q * y1; x = tmp_x; y = tmp_y; } // 循环结束时，a 是 gcd，x, y 是系数 return a; }迭代版的优势是常数小，且没有递归深度限制。在求解单个逆元时差异不大，但在某些需要反复调用的场景或嵌入式环境中可能更有优势。
求模逆元的封装函数：
// 求 a 在模 m 下的逆元，不存在则返回 -1 long long modInv(long long a, long long m) { long long x, y; long long d = exgcd(a, m, x, y); if (d != 1) return -1; // a 和 m 不互质，逆元不存在 // 将 x 调整到 0 ~ m-1 范围内 return (x % m + m) % m; }3.3 欧拉函数的计算与欧拉-费马降幂的实践
欧拉函数 φ(n) 的计算：降幂离不开欧拉函数。计算单个数的欧拉函数，基于其质因数分解： 若 n = p1^k1 * p2^k2 * ... * pm^km，其中 pi 是质数，则 φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pm) 计算过程类似于质因数分解。
long long euler_phi(long long n) { long long ans = n; for (long long p = 2; p * p <= n; ++p) { if (n % p == 0) { ans = ans / p * (p - 1); // 先除后乘防溢出 while (n % p == 0) n /= p; } } if (n > 1) ans = ans / n * (n - 1); // 处理剩余的大质因子 return ans; }欧拉-费马降幂的代码实现：假设我们需要计算 a^b mod m，其中 b 是一个可能非常大的整数（例如以字符串形式给出）。
- 计算 φ(m)。
- 将大整数 b 对 φ(m) 取模，得到余数 r。这里需要一个大整数取模函数。
- 如果 a 与 m 互质，直接计算 a^r mod m。
- 如果使用广义降幂公式，则需要判断 b 与 φ(m) 的大小关系。这通常需要比较 b（大整数）和 φ(m)（普通整数）。如果 b >= φ(m)，则计算 a^(r + φ(m)) mod m。
大整数取模函数示例（字符串形式）：
long long bigMod(const string &b, long long phi) { long long r = 0; for (char digit : b) { r = (r * 10 + (digit - '0')) % phi; } return r; }一个完整的降幂计算示例（假设 a, m 互质）：
long long eulerPow(long long a, const string &b_str, long long m) { if (m == 1) return 0; // 任何数模1为0 long long phi_m = euler_phi(m); long long exp_r = bigMod(b_str, phi_m); // b % φ(m) return fastPow(a, exp_r, m); }实操心得：在竞赛中，如果 m 是质数，那么 φ(m) = m-1，计算起来更简单。另外，对于“指数塔”问题，降幂过程可能需要递归进行，因为指数本身又是一个幂形式。递归的边界是模数 m 变成 1（结果为0）或指数变为可直接计算的小数。
4. 算法实现与代码剖析
4.1 欧拉快速幂的递归实现与矩阵快速幂拓展
除了迭代法，快速幂也可以用递归实现，思路更清晰：
long long fastPowRecur(long long a, long long b, long long m) { if (b == 0) return 1 % m; long long half = fastPowRecur(a, b / 2, m); long long res = (half * half) % m; if (b % 2 == 1) res = (res * a) % m; return res; }递归实现的时间复杂度也是 O(log b)，但会有递归调用开销。它更直观地体现了分治思想：计算 a^b，先计算 a^(b/2)，然后平方，如果b是奇数再乘一个a。
矩阵快速幂：快速幂的思想不仅适用于整数，更适用于任何满足结合律的运算，特别是矩阵乘法。矩阵快速幂是解决线性递推问题（如斐波那契数列第n项）的利器。 假设我们需要计算矩阵 A 的 n 次幂。只需将快速幂中的乘法换成矩阵乘法，单位元1换成单位矩阵 I 即可。
// 假设已定义 Matrix 类并重载了 * 和 % 运算符 Matrix fastMatrixPow(Matrix A, long long n, long long m) { Matrix res = Matrix::identity(A.rows()); // 单位矩阵 while (n > 0) { if (n & 1) res = (res * A) % m; A = (A * A) % m; n >>= 1; } return res; }通过构造合适的转移矩阵，可以用 O(log n) 的时间复杂度计算出原本需要 O(n) 线性时间才能得到的递推数列第n项，这是动态规划优化的常见手段。
4.2 扩展欧几里得解线性同余方程
扩展欧几里得算法最直接的应用就是求解形如ax ≡ b (mod m)的线性同余方程。 方程等价于 ax + my = b。设 d = gcd(a, m)。
- 如果 b 不能被 d 整除，则方程无解。
- 否则，方程有 d 个解。先用exgcd求出 ax + my = d 的一组特解 (x0, y0)。
- 则原方程的一组特解为 x0‘ = x0 * (b / d)。
- 方程在模 m 意义下的全部解为：x = x0‘ + k * (m / d)，其中 k = 0, 1, ..., d-1。
代码示例：
// 求解 ax ≡ b (mod m)，返回一个解，如果无解返回 -1 long long linearCongruence(long long a, long long b, long long m) { long long x, y; long long d = exgcd(a, m, x, y); if (b % d != 0) return -1; // 无解 // 调整特解 x = (x * (b / d)) % m; // 返回最小非负整数解 return (x % (m/d) + (m/d)) % (m/d); }这个函数返回的是模 m/d 意义下的最小非负整数解。如果需要所有解，可以在此基础上生成。
4.3 综合应用：RSA解密过程模拟
RSA公钥加密算法是这三个算法的集大成者。我们来看解密过程如何运用它们。 假设我们已经有了私钥 (d, n) 和密文 c。解密过程是计算m = c^d mod n。
- 指数巨大：私钥指数 d 通常是一个很大的数（几百位），直接计算 c^d 不可能。这里首先使用快速幂作为基础计算单元。
- 模数巨大：n 是两个大质数 p 和 q 的乘积。直接计算 c^d mod n 对于大的 d 和 n 仍然很慢。可以利用中国剩余定理（CRT）进行优化，但这需要知道 p 和 q。优化后需要计算 c^d mod p 和 c^d mod q。
- 降幂？在 RSA 中，我们通常不直接使用欧拉降幂。因为 d 是精心选择的，满足 e*d ≡ 1 (mod φ(n))。解密时我们就是需要计算这个巨大的 d 次幂。快速幂的 O(log d) 复杂度已经足够高效。降幂更多用于指数是变量或未知巨大数的情况。
- 扩展欧几里得：在 RSA 密钥生成过程中，选择 e 后，需要计算 d 使得 e*d ≡ 1 (mod φ(n))。这正是在求 e 模 φ(n) 的逆元，必须使用扩展欧几里得算法。
一个简化的模拟代码框架：
// 假设已有大数类 BigInt 支持相关运算 struct RSAKey { BigInt n; // 模数 BigInt exp; // 指数 (公钥e或私钥d) }; BigInt rsaDecrypt(const BigInt& ciphertext, const RSAKey& privateKey) { // 使用快速幂计算模幂 return fastPowBigInt(ciphertext, privateKey.exp, privateKey.n); } // 密钥生成中计算模逆元 BigInt computeModInverse(const BigInt& e, const BigInt& phi) { // 使用扩展欧几里得算法的大数版本 BigInt x, y; BigInt d = exgcdBigInt(e, phi, x, y); if (d != 1) throw std::runtime_error("e and phi are not coprime"); // 返回最小正逆元 return (x % phi + phi) % phi; }这个例子展示了这些数论算法如何支撑起现代密码学的基石。在实际的 RSA 实现中，还会涉及更多的优化（如 Montgomery 乘法、CRT）和随机数生成、填充方案等，但核心的数论运算离不开我们讨论的这三大算法。
5. 常见问题、优化与排查技巧实录
5.1 快速幂的溢出问题与快速乘
当模数 m 很大（例如接近 10^18）时，即使在long long范围内，计算(a * a) % m也可能在乘法a * a这一步就溢出。解决方案是使用快速乘（或称为“龟速乘”）。
快速乘原理：利用二进制分解和加法，将乘法转化为多次加法取模，防止溢出。
// 计算 (a * b) % m，防止溢出 long long fastMul(long long a, long long b, long long m) { long long res = 0; a %= m; b %= m; while (b > 0) { if (b & 1) res = (res + a) % m; a = (a * 2) % m; // a = a + a b >>= 1; } return res; } // 使用快速乘的快速幂 long long fastPowSafe(long long a, long long b, long long m) { long long res = 1 % m; a %= m; while (b > 0) { if (b & 1) res = fastMul(res, a, m); a = fastMul(a, a, m); b >>= 1; } return res; }快速乘的时间复杂度是 O(log b)，会使快速幂的常数变大。在允许使用__int128（GCC/Clang）的环境下，可以直接用__int128做中间计算然后取模，效率更高：
res = (__int128)res * a % m; a = (__int128)a * a % m;5.2 扩展欧几里得算法解不唯一与最小正解
裴蜀等式 ax + by = gcd(a, b) 的解 (x, y) 不是唯一的。如果 (x0, y0) 是一组特解，那么所有解可以表示为： x = x0 + k * (b / d) y = y0 - k * (a / d) 其中 d = gcd(a, b)，k 为任意整数。
在求模逆元时，我们通常需要的是在 [0, m-1] 范围内的那个解。(x % m + m) % m这个操作可以得到最小非负整数解。但要注意，这是 a 模 m 的逆元，满足 a*x ≡ 1 (mod m)。如果 exgcd 直接求解的是 ax + my = 1，那么得到的 x 可能为负数，调整后即为逆元。
一个常见错误：误以为 exgcd 返回的 x 就是最小正解。它返回的只是满足等式的一组特解，可能为负。务必进行调整。
5.3 欧拉降幂的陷阱与广义公式使用条件
使用欧拉定理降幂有一个重要前提：a 与 m 互质。如果 a 和 m 不互质，a^φ(m) ≡ 1 (mod m) 不成立，不能直接降幂。
错误示例：计算 2^10 mod 4。φ(4)=2。如果错误降幂：10 mod 2 = 0，计算 2^0 mod 4 = 1。但实际 2^10=1024, 1024 mod 4 = 0。结果错误，因为 gcd(2,4)=2 ≠ 1。
此时需要使用广义欧拉降幂公式（指数 b ≥ φ(m) 时）： a^b mod m = a^(b mod φ(m) + φ(m)) mod m 但这个公式在 b < φ(m) 时不适用，需要直接计算。
更保险的降幂计算流程：
long long eulerPowGeneral(long long a, long long b, long long m) { if (m == 1) return 0; if (b == 0) return 1 % m; // a^0 = 1 long long phi = euler_phi(m); if (gcd(a, m) == 1) { // 互质，直接用欧拉定理 return fastPow(a, b % phi, m); } else { // 不互质，使用广义公式，但需判断b大小 if (b < phi) { return fastPow(a, b, m); // 直接算 } else { return fastPow(a, b % phi + phi, m); } } } // 注意：当b是超大数（字符串）时，判断 b < phi 比较麻烦，需要专门的大数比较函数。对于“指数塔” a^(b^(c^(...))) mod m：需要递归应用降幂公式，且递归的每一层都要判断底数与当前模数是否互质，以及指数与 φ(current_mod) 的大小关系。递归边界是模数变为1（结果为0）或指数变为可直接计算的值。这是算法竞赛中的一类经典难题。
5.4 欧拉函数的计算优化与筛法
当需要多次查询欧拉函数值时，使用单个数的分解法效率太低。可以采用线性筛法在 O(n) 时间内预处理出 1~n 所有数的欧拉函数值。
线性筛欧拉函数原理：
- 如果 i 是质数，φ(i) = i-1。
- 遍历质数表，对于每个质数 p：
- 如果 i % p == 0，说明 p 是 i 的质因子，那么 φ(i*p) = φ(i) * p。
- 如果 i % p != 0，说明 p 与 i 互质，那么 φ(i*p) = φ(i) * (p-1)。
代码实现：
const int MAXN = 1000000; int phi[MAXN + 5]; vector<int> primes; bool isPrime[MAXN + 5]; void sieveEuler() { for (int i = 1; i <= MAXN; ++i) { isPrime[i] = true; phi[i] = i; // 初始化 } isPrime[1] = false; phi[1] = 1; for (int i = 2; i <= MAXN; ++i) { if (isPrime[i]) { primes.push_back(i); phi[i] = i - 1; } for (int p : primes) { if (i * p > MAXN) break; isPrime[i * p] = false; if (i % p == 0) { phi[i * p] = phi[i] * p; break; // 线性筛关键：每个合数只被最小的质因子筛掉 } else { phi[i * p] = phi[i] * (p - 1); } } } }预处理之后，查询 φ(n) 就是 O(1) 的操作。这在需要频繁使用欧拉函数的题目中能极大提升效率。
5.5 调试与测试技巧
- 小数据验证：对于快速幂、exgcd，先用小的、容易手算的数据测试，比如计算 2^10 mod 1000，或者解方程 7x ≡ 1 (mod 26) 求逆元。
- 边界测试：
- 快速幂：测试 m=1, b=0, a=0, 大数溢出边界。
- exgcd：测试 a=0, b=0, 负数输入（根据需求处理），以及求逆元时 a 和 m 不互质的情况。
- 欧拉函数：测试 n=1, n=质数, n=质数的幂, n=两个不同质数乘积。
- 对拍：对于复杂的降幂或同余方程求解，可以写一个暴力算法（只适用于小数据范围），与你的优化算法对比结果，随机生成大量数据测试。
- 利用已知性质：
- 费马小定理检验：如果 m 是质数，a^(m-1) mod m 应该等于 1（当 a 不是 m 倍数时）。
- 逆元检验：如果 inv 是 a 模 m 的逆元，那么 (a * inv) % m 应该等于 1。
- 欧拉函数积性：若 gcd(a,b)=1，则 φ(ab) = φ(a)φ(b)。可以用来检验 φ 函数计算是否正确。
我在实际编码中，尤其是在处理模运算时，养成了一个习惯：每一步乘法或加法后，只要有机会，就立刻取模。这能最大程度地避免中间结果溢出带来的隐蔽错误。另外，对于 exgcd 返回的解，永远不要忘记调整到所需的范围，这是一个高频出错点。最后，面对降幂问题，务必先冷静分析 a 与 m 是否互质，再决定使用哪个公式，盲目套用欧拉定理是新手最常见的错误之一。
