HARRIS GREEN HARRIS GREEN

菜单

Harris
发布于 2026-03-23 / 13 阅读
0
0

数论核心：乘法逆元详解与三大算法实现

数论核心：乘法逆元 (Modular Multiplicative Inverse) 详解与算法实现

在算法竞赛和密码学中，我们经常会遇到要求将最终结果对某个大质数（如 10^9+7 或 998244353）取模的情况。 对于加、减、乘法，模运算都满足分配律，我们可以一边计算一边取模。但是，除法是不满足分配律的！

为了在模意义下进行除法运算，我们需要引入 **“乘法逆元”** 的概念。把“除以 a”转化为“乘以 a 的逆元”。

一、 什么是乘法逆元？

在实数域中，除以一个数等于乘以它的倒数（比如除以 5 等于乘以 \frac{1}{5}）。 在模 p 的剩余系中，乘法逆元就是 **“模意义下的倒数”**。

严格定义： 如果存在两个整数 a 和 x，满足：

a \cdot x \equiv 1 \pmod{p}

那么我们就称 x 为 a 在模 p 意义下的乘法逆元，记作 a^{-1} \bmod p。

存在性定理： 在模 p 意义下的乘法逆元存在的充要条件是 a 与 p 互质，即 \gcd(a, p) = 1。

有了逆元，我们计算 \frac{b}{a} \bmod p 就可以转化为：

b \cdot a^{-1} \bmod p

二、 求解逆元的三大核心算法

根据不同的应用场景和数据范围，我们有三种常用的方法来求解逆元。

1. 费马小定理 + 快速幂 (最常用、最容易写)

适用条件：模数 p 必须是质数，且 a 不是 p 的倍数。

原理解析： 根据费马小定理（Fermat's Little Theorem），如果 p 是质数且 a \not\equiv 0 \pmod{p}，则有：

a^{p-1} \equiv 1 \pmod{p}

我们在等式两边同时除以 a（即提取出一个 a）：

a^{p-2} \equiv a^{-1} \pmod{p}

对比逆元的定义 a \cdot a^{-1} \equiv 1 \pmod{p}，可以清晰地看出，a 的逆元就是 a^{p-2} \bmod p。 我们只需用 a 的快速幂算法求出 a^{p-2} \bmod p 即可。

代码实现：

long long qpow(long long base, long long exp, long long p) {
    long long res = 1;
    base %= p;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % p;
        base = (base * base) % p;
        exp >>= 1;
    }
    return res;
}

// 求 a 在模 p 意义下的逆元 (p 必须是质数)
long long getInverse_Fermat(long long a, long long p) {
    return qpow(a, p - 2, p);
}

2. 扩展欧几里得算法 (ExGCD, 最通用)

适用条件：只要 \gcd(a, p) = 1 即可，不需要 p 是质数。

原理解析： 由逆元的定义 a \cdot x \equiv 1 \pmod{p}，它可以转化为一个线性同余方程：

a \cdot x + p \cdot y = 1

因为 \gcd(a, p) = 1，根据裴蜀定理，该方程必然有解。我们可以直接使用扩展欧几里得算法求出 x 和 y。求出的 x 就是 a 的逆元。 ( 注意：ExGCD 求出的 x 可能是负数，需要将其调整到 [0, p) 的范围内 )。

代码实现：

// 扩展欧几里得算法
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);
    y -= (a / b) * x;
    return d;
}

// 求 a 在模 p 意义下的逆元 (只需 a, p 互质)
long long getInverse_ExGCD(long long a, long long p) {
    long long x, y;
    long long d = exgcd(a, p, x, y);
    if (d != 1) return -1; // 不互质，逆元不存在
    return (x % p + p) % p; // 保证返回正数逆元
}

3. 线性递推求逆元 (适用于打表)

适用条件：模数 p 是质数。需要一次性求出 1 到 n 所有连续数字的逆元，且 n < p。

原理解析： 如果对每个数都用快速幂求逆元，复杂度是 O(n \log p)，在 n 极大时会超时。我们可以利用前面已知的逆元，在 O(n) 时间内递推出后面的逆元。

设 p = k \cdot i + r，其中 r = p \bmod i，k = \lfloor p / i \rfloor。 在模 p 意义下：

k \cdot i + r \equiv 0 \pmod{p} \Rightarrow r \equiv -k \cdot i \pmod{p}

两边同时乘以 i^{-1} \cdot r^{-1}：

i^{-1} \equiv -k \cdot r^{-1} \pmod{p}

代入 k = \lfloor p / i \rfloor 和 r = p \bmod i 的定义，得到终极递推式：

\text{inv}[i] = (p - \lfloor p / i \rfloor) \cdot \text{inv}[p \bmod i] \bmod p

( 注：用 p - \lfloor p / i \rfloor 代替 -\lfloor p / i \rfloor 是为了防止出现负数取模的问题 )。

代码实现：

#include <vector>
using namespace std;

// O(n) 求 1 到 n 的所有逆元
vector<long long> getInverse_Linear(int n, long long p) {
    vector<long long> inv(n + 1);
    inv[1] = 1; // 1 的逆元永远是 1
    for (int i = 2; i <= n; ++i) {
        inv[i] = (p - p / i) * inv[p % i] % p;
    }
    return inv;
}

三、 实战应用：组合数取模

逆元最经典的应用场景就是求组合数 C(n, m) = \frac{n!}{m!(n-m)!}：

在程序中，我们无法先做除法再取模。正确的做法是：

  1. 预处理出阶乘数组 fact[i]。
  2. 预处理出阶乘的逆元数组 invFact[i]。
  3. 公式转化为乘法：​C(n, m) = \text{fact}[n] \cdot \text{invFact}[m] \cdot \text{invFact}[n - m] \bmod p。
long long C(int n, int m, long long p) {
    if (m < 0 || m > n) return 0;
    return fact[n] * invFact[m] % p * invFact[n - m] % p;
}

总结

  • 单个逆元，且 ​p 为质数 → 费马小定理 (快速幂)
  • 单个逆元，但 ​p 不是质数 → 扩展欧几里得 (ExGCD)
  • 批量求 ​1 \sim n 的逆元 → 线性递推公式
深入浅出杨表：从组合数学到算法降维打击
围棋状态空间复杂度的数学推导与计算

评论