企业官网建设流程全解析

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 b=MOD; // int 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; //}

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 M

3.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. 方法对比与选择建议

5. 实际应用场景

• 组合数取模：计算C(n, k) mod p（p 为质数）时，需要用到阶乘的逆元。
• 线性同余方程：求解ax ≡ b (mod M)时，若gcd(a, M) = 1，则x ≡ b × a⁻¹ (mod M)。
• 密码学：RSA 算法中私钥的计算涉及模逆元。

6. 注意事项

1. 使用扩展欧几里得算法时，务必检查gcd(a, M) = 1，否则逆元不存在。
2. 费马小定理方法仅当M为质数时成立，使用时需确保模数是质数。
3. 计算结果可能为负数，需要通过(x % M + M) % M转换为正数。
4. 对于大数运算，注意使用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; }