模逆元计算方法详解：扩展欧几里得算法与费马小定理

1. 模逆元简介在模运算中对于整数a和模数M如果存在整数x使得a × x ≡ 1 (mod M)则称x为a在模M下的逆元记作a⁻¹或inv(a)。模逆元在密码学、组合数学和算法竞赛中有着广泛应用。2. 方法一扩展欧几里得算法通用方法扩展欧几里得算法适用于M和a互质即gcd(a, M) 1的情况。该算法不仅能求出最大公约数还能求出贝祖等式ax by gcd(a, b)的一组整数解。2.1 算法实现以下是扩展欧几里得算法的 C 实现// 扩展欧几里得算法求 ax by gcd(a,b) 的解 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 x1, y1; long long d exgcd(b, a % b, x1, y1); x y1; y x1 - (a / b) * y1; return d; } // 求 a 在模 M 下的逆元 long long mod_inv(long long a, long long M) { long long x, y; long long d exgcd(a, M, x, y); if (d ! 1) return -1; // 不存在逆元 return (x % M M) % M; // 保证结果为正 } //简洁点的 //long long inv_exgcd(long long a, long long b){ // long long bMOD; // int u1, v0; // while(b) { // long long ta/b; // a-t*b; // swap(a,b); // u-t*v; // swap(u,v); // } // return (u%MODMOD)%MOD; //}2.2 算法原理当gcd(a, M) 1时扩展欧几里得算法求出的x满足ax My 1。对等式两边取模M得到ax ≡ 1 (mod M)因此x就是a在模M下的逆元。2.3 示例求 2 在模 7 下的逆元2 × 4 8 ≡ 1 (mod 7) 所以 2⁻¹ 4使用上述代码计算mod_inv(2, 7)返回 4。3. 方法二费马小定理适用于质数模数当模数M是质数时根据费马小定理a^(M-1) ≡ 1 (mod M)因此a⁻¹ a^(M-2) mod M3.1 快速幂实现以下是使用快速幂计算模逆元的 C 实现long long mod_pow(long long a, long long b, long long mod) { long long res 1; while (b 0) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; } // 求 a 在质数模 M 下的逆元 long long mod_inv_prime(long long a, long long M) { return mod_pow(a, M - 2, M); }3.2 时间复杂度快速幂的时间复杂度为 O(log M)当M很大时如 10⁹7这种方法比扩展欧几里得算法稍慢但代码更简洁。4. 方法对比与选择建议方法适用条件时间复杂度优点缺点扩展欧几里得gcd(a, M) 1O(log min(a, M))通用性强可判断逆元是否存在代码稍复杂费马小定理M为质数O(log M)代码简洁易于实现仅适用于质数模数5. 实际应用场景组合数取模计算C(n, k) mod pp 为质数时需要用到阶乘的逆元。线性同余方程求解ax ≡ b (mod M)时若gcd(a, M) 1则x ≡ b × a⁻¹ (mod M)。密码学RSA 算法中私钥的计算涉及模逆元。6. 注意事项使用扩展欧几里得算法时务必检查gcd(a, M) 1否则逆元不存在。费马小定理方法仅当M为质数时成立使用时需确保模数是质数。计算结果可能为负数需要通过(x % M M) % M转换为正数。对于大数运算注意使用long long类型避免溢出。7.完整模板代码#include bits/stdc.h using namespace std; const long long MOD 998244353; // 方法1快速幂求逆元模数为质数 long long inv_fermat(long long a) { long long res 1, base a, exp MOD - 2; while (exp 0) { if (exp 1) res res * base % MOD; base base * base % MOD; exp 1; } return res; } // 方法2扩展欧几里得求逆元通用 long long inv_exgcd(long long a) { long long b MOD, u 1, v 0; while (b) { long long t a / b; a - t * b; swap(a, b); u - t * v; swap(u, v); } return (u % MOD MOD) % MOD; } int main() { // 计算 15/2 long long inv2 inv_fermat(2); cout 15 * inv2 % MOD endl; // 499122184 // 计算 5/3 long long inv3 inv_fermat(3); cout 5 * inv3 % MOD endl; return 0; }