CC++ & Algorithm

模逆元的概念与性质

困难4
语言版本：通用
概述：模逆元就像是在模运算世界里的“倒数”，能帮我们解决除法问题；只有两个数互质时，逆元才存在。

模逆元：模运算世界里的“倒数”

同学们，你们有没有遇到过这样的问题：在数学课上，计算 2 除以 3 得到分数 2/3，而编程中整数除法会丢掉小数部分（比如 5 / 2 得 2）。更麻烦的是，在模运算（只关心余数的世界）里，普通的除法根本不能直接使用！比如我们要计算 “10 除以 3，结果对 7 取余”，按分数算 10/3 ≈ 3.333，但模世界里只允许整数结果，那该怎么办？模逆元就是来帮我们解决这个问题的——它就像模运算里的“倒数”，能把除法变成乘法，让计算变成整数操作。

1. 模逆元是什么？——从“倒数”到“模倒数”

生活中的“还原”比喻

想象一把密码锁：钥匙 A 锁上，钥匙 B 打开，锁上后再用开锁钥匙就“还原”了。数字世界里也有类似的关系：一个数乘以它的“逆元”就会得到 1。在普通算术中，3 的逆元是 1/3，因为 3 × 1/3 = 1。但在模运算中，我们只考虑整数，而且结果要取余数。比如在模 7 的世界里，3 的逆元是 5，因为 3 × 5 = 15，15 ÷ 7 余 1（15 mod 7 = 1）。

时钟就是模 12 的世界：假设现在是 3 点，你想往回拨 4 小时，但只能向前拨。你可以向前拨 8 小时，因为 3 + 8 = 11，这和 3 - 4 = -1，再加 12 得 11 是一样的。这里的 8 就是 4 的“加法逆元”。今天我们讲的是乘法逆元，就像寻找一个数，使得两者相乘后模某个数等于 1。

数学定义

设正整数 aa 和模数 mm，如果存在整数 xx 使得：

a⋅x≡1(modm)a \cdot x \equiv 1 \pmod{m}

那么 xx 就叫做 aa 在模 mm 下的模逆元，记作 a−1(modm)a^{-1} \pmod{m} 或 inv(a)。

注意：这里的 aa 和 mm 必须互质（最大公约数为 1），否则逆元不存在。为什么呢？因为如果它们有公因数 d > 1，那么 a × x 永远都是 d 的倍数，而 1 不是 d 的倍数，所以不可能模 m 等于 1。

新手常见错误 1：以为任何数都有逆元

很多同学会想：“2 在普通算术里有倒数 0.5，那在模 6 下也应该有吧？” 其实不对！2 和 6 的最大公约数是 2，不互质，所以没有逆元。只有和模数互质的数才可能有逆元。

2. 模逆元的性质——四个要点要记牢

  1. 唯一性：如果逆元存在，那么它在模 m 的 0~m-1 范围内是唯一的。比如 3 在模 7 下的逆元只能是 5，不会同时是 12（因为 12 mod 7 = 5）。

  2. 互异性：不同的 a 对应不同的逆元，不会出现两个不同的数共享同一个逆元的情况（除非它们本身相等）。

  3. 可逆性：a 的逆元的逆元就是 a 本身。就像 -(-3) = 3，在模世界也一样：inv(inv(a)) = a。

  4. 与除法的关系：有了逆元，我们就可以把模运算中的除法变成乘法：

    ab(modm)等价于a×inv(b)(modm)\frac{a}{b} \pmod{m} \quad \text{等价于} \quad a \times \text{inv}(b) \pmod{m}

    这非常有用，因为模运算里没有直接的除法运算符。

3. 如何求模逆元？四种方法由浅入深

方法一：暴力枚举法（适合理解概念）

最简单的想法：从 1 试到 m-1，看看哪个数 x 满足 a * x mod m == 1。当然，当 m 很大时这个方法很慢，但用来理解概念非常直观。

C++ 代码示例

#include <iostream>
using namespace std;

/**
 * 暴力求模逆元
 * @param a 要求逆元的数
 * @param m 模数
 * @return 如果存在逆元，返回最小正整数逆元；否则返回 -1
 */
int modInverseBruteForce(int a, int m) {
    a = a % m;           // 确保 a 在 0~m-1 范围内
    for (int x = 1; x < m; x++) {
        if ((a * x) % m == 1) { // 检查余数是否为 1
            return x;    // 找到逆元
        }
    }
    return -1;           // 没有找到，说明 a 和 m 不互质
}

int main() {
    int a = 3, m = 7;
    int inv = modInverseBruteForce(a, m);
    if (inv != -1) {
        cout << a << " 在模 " << m << " 下的逆元是 " << inv << endl;
        // 验证：3 * 5 = 15，15 % 7 = 1
    } else {
        cout << "逆元不存在" << endl;
    }
    return 0;
}

Python 代码示例

def mod_inverse_bruteforce(a, m):
    """
    暴力求模逆元
    a: 要求逆元的数
    m: 模数
    返回: 如果存在逆元，返回最小正整数逆元；否则返回 -1
    """
    a = a % m  # 确保 a 在 0~m-1 范围内
    for x in range(1, m):
        if (a * x) % m == 1:  # 检查余数是否为 1
            return x
    return -1  # 没有找到逆元

# 测试
a = 3
m = 7
inv = mod_inverse_bruteforce(a, m)
if inv != -1:
    print(f"{a} 在模 {m} 下的逆元是 {inv}")
else:
    print("逆元不存在")

方法二：费马小定理（适合模数为质数）

当模数 p 是质数时，数学家费马发现了一个简单的规律：如果 a 不是 p 的倍数，那么 ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}。等式两边同时除以 a（即乘以逆元），就得到：

ap−2≡a−1(modp)a^{p-2} \equiv a^{-1} \pmod{p}

所以，a 的逆元就是 ap−2 mod pa^{p-2} \bmod p。结合快速幂算法（O(log p)），我们可以高效求解。

快速幂的原理

快速幂把指数写成二进制形式，比如计算 3133^{13}，13 的二进制是 1101，即 38×34×313^8 \times 3^4 \times 3^1。我们不断平方底数，并根据二进制位决定是否乘入结果，只需 O(log exponent) 次乘法。

C++ 实现：快速幂 + 费马小定理

#include <iostream>
using namespace std;

typedef long long ll; // 使用 long long 防止乘法溢出

// 快速幂：计算 base^exp mod mod
ll fastPow(ll base, ll exp, ll mod) {
    ll result = 1;
    base = base % mod;  // 防止 base 太大
    while (exp > 0) {
        if (exp & 1) {               // 如果当前二进制位为 1
            result = (result * base) % mod;
        }
        base = (base * base) % mod;   // base 平方，准备下一位
        exp >>= 1;                    // 指数右移一位
    }
    return result;
}

// 利用费马小定理求逆元，前提：mod 是质数，且 a 不是 mod 的倍数
ll modInverseFermat(ll a, ll p) {
    return fastPow(a, p - 2, p);      // a^(p-2) mod p
}

int main() {
    ll a = 3, p = 7;
    ll inv = modInverseFermat(a, p);
    cout << a << " 在模 " << p << " 下的逆元是 " << inv << endl;
    // 验证：3 * 5 = 15，15 % 7 = 1
    return 0;
}

Python 实现

def fast_pow(base, exp, mod):
    """快速幂计算 base^exp % mod"""
    result = 1
    base = base % mod
    while exp > 0:
        if exp & 1:                # 如果最低位为 1
            result = (result * base) % mod
        base = (base * base) % mod  # 平方
        exp >>= 1                   # 右移一位
    return result

def mod_inverse_fermat(a, p):
    """费马小定理求逆元，p 必须是质数且 a 不是 p 的倍数"""
    return fast_pow(a, p - 2, p)

# 测试
a = 3
p = 7
inv = mod_inverse_fermat(a, p)
print(f"{a} 在模 {p} 下的逆元是 {inv}")

新手常见错误 2：在非质数模上使用费马小定理

如果模数不是质数（比如 m=15），费马小定理不成立。这时计算 a^(m-2) 并不可靠。比如 a=2, m=15，2^(15-2)=2^13=8192，8192 mod 15 = 2，并不是 2 的逆元（真实逆元是 8）。所以一定要确认模数是质数再使用。

方法三：扩展欧几里得算法（通用解法，模数不必是质数）

求 a 在模 m 下的逆元，就是求解同余方程 ax≡1(modm)a x \equiv 1 \pmod{m}，即存在整数 y 使得：

ax+my=1a x + m y = 1

这正是贝祖定理的形式：当 a 和 m 互质时（gcd=1），方程一定有整数解。扩展欧几里得算法能求出 x 和 y，其中的 x 就是逆元（可能为负数，需调整为 0~m-1 的正数）。

算法推导（递归思想）

欧几里得算法：gcd⁡(a,m)=gcd⁡(m,a mod m)\gcd(a,m) = \gcd(m, a \bmod m)。我们递归调用扩展欧几里得(m, r) 得到一组解 (x1, y1) 满足：

m⋅x1+r⋅y1=1m \cdot x_1 + r \cdot y_1 = 1

将 r=a−m⋅qr = a - m \cdot q（其中 q=a//mq = a//m）代入，整理后得到：

a⋅y1+m⋅(x1−q⋅y1)=1a \cdot y_1 + m \cdot (x_1 - q \cdot y_1) = 1

所以新的解为：x=y1,  y=x1−q⋅y1x = y_1,\; y = x_1 - q \cdot y_1。递归边界是当 m=0 时，返回 x=1, y=0。

举例：求 3 在模 7 下的逆元

  • 调用 exgcd(3,7)：q=0, r=3 → 递归 exgcd(7,3)
    • exgcd(7,3)：q=2, r=1 → 递归 exgcd(3,1)
      • exgcd(3,1)：q=3, r=0 → 递归 exgcd(1,0) 返回 (x=1,y=0)
      • 回溯得 x=0, y=1
    • 回溯得 x=1, y=-2
  • 回溯得 x=-2, y=1 所以一组解为 3×(-2)+7×1=1，x=-2，调整为正数：-2+7=5，逆元为 5。

C++ 实现

#include <iostream>
using namespace std;

typedef long long ll;

// 扩展欧几里得算法，返回 gcd，同时通过引用返回 x,y 满足 ax+by=gcd
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll gcd = exgcd(b, a % b, x, y);
    ll temp = x;       // 保存旧的 x
    x = y;             // 新 x = 旧 y
    y = temp - (a / b) * y; // 新 y = 旧 x - (a/b)*旧 y
    return gcd;
}

// 用扩展欧几里得求 a 在模 m 下的逆元，要求 gcd(a,m)=1
ll modInverseExgcd(ll a, ll m) {
    ll x, y;
    ll g = exgcd(a, m, x, y);
    if (g != 1) return -1;          // 逆元不存在
    return (x % m + m) % m;         // 调整到 [0, m-1] 范围
}

int main() {
    ll a = 3, m = 7;
    ll inv = modInverseExgcd(a, m);
    if (inv != -1)
        cout << a << " 在模 " << m << " 下的逆元是 " << inv << endl;
    else
        cout << "逆元不存在" << endl;
    return 0;
}

Python 实现

def exgcd(a, b):
    """扩展欧几里得，返回 (gcd, x, y) 使得 a*x + b*y = gcd"""
    if b == 0:
        return a, 1, 0
    gcd, x1, y1 = exgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return gcd, x, y

def mod_inverse_exgcd(a, m):
    """扩展欧几里得求逆元，需 gcd(a,m)=1"""
    g, x, y = exgcd(a, m)
    if g != 1:
        return -1
    return (x % m + m) % m  # 调整为正数

# 测试
a = 3
m = 7
inv = mod_inverse_exgcd(a, m)
if inv != -1:
    print(f"{a} 在模 {m} 下的逆元是 {inv}")
else:
    print("逆元不存在")

方法四：线性预处理逆元（批量生产逆元，适合质数模）

当我们需要求很多个数的逆元（比如 1 到 n 全部逆元），逐个用快速幂或扩展欧几里得会太慢。这时可以用一个巧妙的递推公式，在 O(n) 时间内全部算出来。

假设模数 p 是质数，且 n < p，那么对于任意 i（1 ≤ i < p），有：

inv[i]=p−(⌊pi⌋×inv[p mod i]) mod p\text{inv}[i] = p - \left( \left\lfloor \frac{p}{i} \right\rfloor \times \text{inv}[p \bmod i] \right) \bmod p

初始 inv[1] = 1。因为 p % i 小于 i，所以从 2 到 n 可以依次递推。

举例：模 p=7，求 1~6 的逆元

  • inv[1] = 1
  • i=2: p//i=3, p%i=1, inv[2]=7-(3*1%7)=4
  • i=3: p//i=2, p%i=1, inv[3]=7-(2*1%7)=5
  • i=4: p//i=1, p%i=3, inv[4]=7-(1*5%7)=2
  • i=5: p//i=1, p%i=2, inv[5]=7-(1*4%7)=3
  • i=6: p//i=1, p%i=1, inv[6]=7-(1*1%7)=6

验证：2×4=8≡1, 3×5=15≡1, 4×2=8≡1, 5×3=15≡1, 6×6=36≡1 mod7。正确！

C++ 实现

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

// 线性预处理 [1,n] 每个数在模 p 下的逆元，p 为质数且 n < p
vector<ll> linearInverse(int n, ll p) {
    vector<ll> inv(n + 1); // 下标从 1 开始
    inv[1] = 1;             // 1 的逆元是 1
    for (int i = 2; i <= n; i++) {
        // 递推公式：inv[i] = p - (p/i) * inv[p%i] % p
        inv[i] = p - (p / i) * inv[p % i] % p;
    }
    return inv;
}

int main() {
    ll p = 7;
    int n = 6;
    vector<ll> inv = linearInverse(n, p);
    cout << "模 " << p << " 下 1~" << n << " 的逆元:" << endl;
    for (int i = 1; i <= n; i++) {
        cout << i << " -> " << inv[i] << endl;
    }
    return 0;
}

Python 实现

def linear_inverse(n, p):
    """线性预处理 1..n 在模 p 下的逆元，p 为质数且 n < p"""
    inv = [0] * (n + 1)
    inv[1] = 1
    for i in range(2, n + 1):
        # 递推公式：inv[i] = p - (p // i) * inv[p % i] % p
        inv[i] = p - (p // i) * inv[p % i] % p
    return inv

p = 7
n = 6
inv = linear_inverse(n, p)
print(f"模 {p} 下 1~{n} 的逆元:")
for i in range(1, n + 1):
    print(f"{i} -> {inv[i]}")

新手常见错误 3：线性递推时 n 大于等于 p

递推公式要求 n < p，否则 p % i 可能为 0，导致 inv[0] 未定义（0 没有逆元）。另外，如果 p 不是质数，递推中的 inv[p%i] 可能不存在，所以通常只用于质数模。

4. 逆元的实际应用——组合数计算

现在我们来个经典应用：计算组合数 C(n, k) 模一个大质数。组合数公式：

C(n,k)=n!k!(n−k)!C(n, k) = \frac{n!}{k! (n-k)!}

模运算下，除法要变成乘以分母的逆元。我们通过预处理阶乘和逆阶乘来 O(1) 查询。

预处理方法（常用）

  1. 计算阶乘 fac[i] = i! mod p。
  2. 用费马小定理求出 fac[n] 的逆元 inv_fac[n] = fac[n]^(p-2) mod p。
  3. 逆推：inv_fac[i-1] = inv_fac[i] * i mod p。

然后组合数 = fac[n] * inv_fac[k] % p * inv_fac[n-k] % p。

完整模板（以常见模数 1e9+7 为例）

C++ 实现

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
const ll MOD = 1000000007; // 一个大质数

ll fastPow(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

vector<ll> fac, inv_fac;

void init(int n) {
    fac.resize(n + 1);
    inv_fac.resize(n + 1);
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % MOD; // 计算阶乘
    }
    // 用费马小定理求 fac[n] 的逆元
    inv_fac[n] = fastPow(fac[n], MOD - 2);
    // 逆推逆阶乘
    for (int i = n; i >= 1; i--) {
        inv_fac[i - 1] = inv_fac[i] * i % MOD;
    }
}

ll combination(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fac[n] * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
}

int main() {
    int n = 5, k = 2;
    init(n);
    ll ans = combination(n, k);
    cout << "C(" << n << "," << k << ") mod " << MOD << " = " << ans << endl;
    return 0;
}

Python 实现

MOD = 1000000007

def fast_pow(base, exp):
    """快速幂"""
    res = 1
    base %= MOD
    while exp > 0:
        if exp & 1:
            res = (res * base) % MOD
        base = (base * base) % MOD
        exp >>= 1
    return res

def init_factorials(n):
    """预处理阶乘和逆阶乘，返回 (fac, inv_fac)"""
    fac = [1] * (n + 1)
    for i in range(1, n + 1):
        fac[i] = fac[i - 1] * i % MOD
    inv_fac = [1] * (n + 1)
    inv_fac[n] = fast_pow(fac[n], MOD - 2)
    for i in range(n, 0, -1):
        inv_fac[i - 1] = inv_fac[i] * i % MOD
    return fac, inv_fac

def combination(n, k, fac, inv_fac):
    """返回 C(n, k) % MOD"""
    if k < 0 or k > n:
        return 0
    return fac[n] * inv_fac[k] % MOD * inv_fac[n - k] % MOD

# 测试
n, k = 5, 2
fac, inv_fac = init_factorials(n)
ans = combination(n, k, fac, inv_fac)
print(f"C({n},{k}) mod {MOD} = {ans}")

常见错误 4：没有判断 n < p 直接使用阶乘预处理

如果 n >= p，阶乘中会出现 p 的倍数，导致 fac[n] 为 0，后面的逆元计算也会出问题。这时需要用到卢卡斯定理（Lucas Theorem）。初学者在题目中遇到时要特别注意模数是否大于 n。

5. 相关指引与进阶学习

通过以上内容，你已经掌握了模逆元的核心概念、四种求法（暴力、费马小定理、扩展欧几里得、线性预处理）以及经典应用（组合数计算）。接下来你可以继续学习：

  • 卢卡斯定理：当 n 和 k 很大且模数 p 是质数但不够大时的组合数计算。
  • 中国剩余定理：解一次同余方程组，也需要求逆元。
  • 概率与期望中的模运算：比如抽卡概率问题，分数取模都会用到逆元。

逆元是数论在编程竞赛中的基石，熟练掌握它，你就能解决很多看似复杂的取模问题。快去试试用逆元自己写一个求概率的题目吧！

例题精讲

1单选题

在模15运算中，以下哪个数存在模逆元？

A3
B5
C7
D9
2判断题

在模运算中，如果整数a存在模m的逆元，那么a与m一定互质。

3判断题

对于任意正整数m，所有小于m的非负整数都存在模m的逆元。

4填空题
以下函数使用扩展欧几里得算法求模逆元，返回-1表示逆元不存在。请填写缺失的表达式，使得函数正确返回a在模m下的逆元（保证结果在[0, m-1]范围内）。

int modInverse(int a, int m) {
    int x, y;
    int g = extendedGcd(a, m, x, y);
    if (g != 1) return -1;
    else return ___;
}

（注：extendedGcd函数返回gcd(a,m)，并设置x,y满足ax + my = g）
5填空题
下面函数用于判断整数a在模m下是否存在逆元。请填写条件表达式，使得函数正确返回true或false。

bool hasInverse(int a, int m) {
    return ___ == 1;
}