高效求解模运算中的乘法逆元

核心逻辑与数学原理

乘法逆元是模意义下除法运算的替代工具。若整数 $a, m$ 互质，且满足同余方程：

$$a \cdot x \equiv 1 \pmod m$$

则称 $x$ 为 $a$ 在模 $m$ 意义下的乘法逆元，记作 $a^{-1}$。在模意义下，除以一个数等于乘以该数的逆元，即 $\frac{b}{a} \equiv b \cdot a^{-1} \pmod m$。

求取逆元有三种核心数学路径：

费马小定理（Fermat's Little Theorem）：若 $m$ 为质数，且 $\gcd(a, m) = 1$，则有 $a^{m-1} \equiv 1 \pmod m$。两边同除以 $a$ 变形得：

$$a \cdot a^{m-2} \equiv 1 \pmod m$$

由此可知，$a^{-1} = a^{m-2} \bmod m$。通过快速幂算法可在 $O(\log m)$ 时间内求解。

扩展欧几里得算法（EXGCD）：若 $m$ 不为质数，但保证 $\gcd(a, m) = 1$，费马小定理失效。此时将同余方程转化为二元一次不定方程：

$$a \cdot x + m \cdot y = 1$$

直接运行 $EXGCD$ 求解 $x$，时间复杂度为 $O(\log \min(a, m))$。

线性递推求逆元：当需要求 $1 \sim N$ 所有关于质数 $p$ 的逆元时，若对每个数单独求解，复杂度为 $O(N \log p)$，在 $N \ge 10^6$ 时会超时。利用数学递推，可以在 $O(N)$ 时间内离线处理出所有逆元。

算法推导与状态设计

线性逆元递推公式推导

设当前需要求 $i$ 在模 $p$ 意义下的逆元（$p$ 为质数，且 $i < p$）。令 $k = \lfloor \frac{p}{i} \rfloor$，$r = p \bmod i$。由此可得：

$$p = k \cdot i + r$$

在模 $p$ 意义下，有：

$$k \cdot i + r \equiv 0 \pmod p$$

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

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

移项变形，将 $i^{-1}$ 孤立到等式左边：

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

将 $k = \lfloor \frac{p}{i} \rfloor$ 和 $r = p \bmod i$ 带回等式：

$$i^{-1} \equiv -\lfloor \frac{p}{i} \rfloor \cdot (p \bmod i)^{-1} \pmod p$$

为了消除负号，将其转化为正数模：

$$i^{-1} \equiv (p - \lfloor \frac{p}{i} \rfloor) \cdot (p \bmod i)^{-1} \pmod p$$

设 $inv[i]$ 为 $i$ 的逆元，则状态转移方程为：

$$inv[i] = (p - p / i) \cdot inv[p \bmod i] \bmod p$$

由于 $p \bmod i < i$，其逆元必然在之前已经算出，满足无后效性。边界条件为 $inv[1] = 1$。

C++ 标准源码

#include <iostream>
#include <vector>

// 1. 快速幂求逆元（费马小定理），适用前提：p 为质数 且 a 与 p 互质
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

long long get_inv_fermat(long long a, long long p) {
    return power(a, p - 2, p);
}

// 2. EXGCD 求逆元，适用前提：a 与 m 互质（m 可不为质数）
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 g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

long long get_inv_exgcd(long long a, long long m) {
    long long x, y;
    long long g = exgcd(a, m, x, y);
    if (g != 1) return -1; // gcd(a, m) != 1 则逆元不存在
    return (x % m + m) % m;
}

// 3. 线性递推求 1~n 的逆元，适用前提：p 为质数 且 n < p
void get_all_inv(int n, long long p, std::vector<long long> &inv) {
    inv.resize(n + 1);
    inv[1] = 1; // 边界：1 的逆元永远是 1
    for (int i = 2; i <= n; ++i) {
        // 防止 (p - p / i) * inv[p % i] 乘法溢出，必须强制转 long long
        inv[i] = (p - p / i) * inv[p % i] % p;
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    long long p;
    if (std::cin >> n >> p) {
        std::vector<long long> inv;
        get_all_inv(n, p, inv);
        for (int i = 1; i <= n; ++i) {
            std::cout << inv[i] << "\n";
        }
    }
    return 0;
}

NOIP 实战避坑指南

盲目套用费马小定理导致零解 当模数 $m$ 不是质数（如常见的部分非质数大模数），或者 $a$ 是 $m$ 的倍数时，使用 power(a, m - 2, m) 会算出一个错误的垃圾数据，甚至在 $a \equiv 0 \pmod m$ 时输出 $0$ 作为逆元，直接破坏后续所有乘法逻辑。必须在调用前明确模数性质，非质数一律用 $EXGCD$。
线性递推中越界使用 p % i 在线性递推求逆元时，循环范围必须严格限制在 $i < p$。如果输入的 $n \ge p$，那么当 $i = p$ 时，p % i 会变成 $0$，而 inv[0] 未定义（或为 0），会导致后续所有的 inv 数组项全部塌陷为 $0$。

经典 NOIP/洛谷真题

1. 洛谷 P3811 【模板】乘法逆元

题意描述：给定正整数 $N$ 和一个质数 $P$，求 $1 \sim N$ 所有正整数在模 $P$ 意义下的乘法逆元。数据范围 $N \le 3 \times 10^6, P \le 2 \times 10^9$。
问题本质：高时限要求下的单点逆元批处理。
核心解题思路：若使用快速幂或 $EXGCD$，总复杂度为 $O(N \log P)$，在此数据规模下必超时。直接应用状态转移方程 inv[i] = (p - p / i) * inv[p % i] % p 进行一维线性 DP，空间使用 std::vector 或预分配数组，时空复杂度均优化至 $O(N)$。

2. 洛谷 P5431 【模板】乘法逆元 2

题意描述：给定 $N$ 个正整数 $a_1, a_2, \dots, a_n$，一个质数 $P$ 以及一个常数 $K$，求 $\sum_{i=1}^{n} \frac{K^i}{a_i} \pmod P$。数据范围 $N \le 5 \times 10^6$。
问题本质：任意输入序列的线性时间逆元求解（离线逆元）。
核心解题思路：这题不能直接递推。需先计算 $a_i$ 的前缀积 $s_i = \prod_{j=1}^i a_j$。接着用快速幂求出总乘积的逆元 $sv_n = (s_n)^{-1}$。利用逆元倒推性质：$sv_{i-1} = sv_i \cdot a_i \pmod P$，在 $O(N)$ 时间内反向递推出所有前缀积的逆元。最后，单个元素的逆元可直接通过 $a_i^{-1} = sv_i \cdot s_{i-1} \pmod P$ 在 $O(1)$ 内获取。整个算法仅需一次快速幂，其余均为线性扫描。