线性预处理逆元：批量计算模逆元的“速算法”

1. 从“倒数”说起——为什么要学模逆元？

同学们，你们还记得小学学的倒数吗？一个数 $a$ 的倒数是 $\frac{1}{a}$，因为 $a \times \frac{1}{a} = 1$。比如，3 的倒数是 $\frac{1}{3}$，3 乘以它等于 1。

在编程和数学里，我们经常要在模运算中做“除法”。什么是模运算？简单说就是“取余数”。比如，我们想计算 $3 \div 2$，但要求结果是一个整数，而且是在某个模数 $p$（比如 7）的意义下。这时候，我们就要用模逆元。

生活小例子：假设你有 10 颗糖，要平均分给 3 个朋友，每人分 3 颗，还剩 1 颗。这个“除以 3”在模 10 的世界里可就不一样了。如果模数是 7，那么“除以 3”相当于找到某个数 $x$，使得 $3 \times x$ 除以 7 的余数等于 1。这个 $x$ 就是 3 的模逆元。

一个数 $a$ 的模逆元（记作 $\text{inv}[a]$）满足：

这里“$\equiv$”表示两边除以 $p$ 的余数相等。比如在模 7 下，3 的逆元是多少？因为 $3 \times 5 = 15$，$15 \bmod 7 = 1$，所以 $\text{inv}[3] = 5$。

2. 为什么需要“线性预处理”？

在写代码时，我们常常要反复计算很多数的逆元。比如，要算 $1$ 到 $1000000$ 里每个数的模逆元，如果用费马小定理或扩展欧几里得算法一个一个求，每个数需要 $O(\log p)$ 时间，总共 $O(n \log p)$，当 $n$ 和 $p$ 都很大时（比如 $n=10^7, p=10^9+7$），速度就太慢了。

有没有更快的办法？有的！我们可以用一个巧妙的递推公式，用已经算好的较小数的逆元来推出当前数的逆元，这样只需要 $O(n)$ 时间就能得到所有逆元。这就是“线性预处理逆元”。

生活类比：就像你提前把 1 到 100 的倒数都打印在一张表上，以后每次需要某个数的倒数，直接查表，不用再重新算。这个“提前算好所有倒数”的过程就是线性预处理。

3. 数学原理与公式推导（附生活化理解）

假设模数 $p$ 是一个质数（比如 7、13、998244353 等）。对于任意整数 $i$（$1 \le i < p$），我们想求 $\text{inv}[i]$。

第一步：把 $p$ 写成带余除法的形式

例如，$p=7, i=3$，则 $k = 2, r = 1$，因为 $7 = 2\times 3 + 1$。

生活理解：想象你有一盘蛋糕（大小 $p$），要分给 $i$ 个朋友，每人分 $k$ 块，最后还剩 $r$ 块。这个“剩的” $r$ 比 $i$ 小，所以我们可以用已经算好的逆元来帮忙。

第二步：对等式两边取模 $p$

因为 $p$ 本身除以 $p$ 余 0，所以左边也等于 0 模 $p$。

第三步：两边同乘 $\text{inv}[i] \times \text{inv}[r]$

注意，因为 $p$ 是质数，只要 $i$ 和 $r$ 不是 $p$ 的倍数，它们的逆元就存在。我们把等式两边都乘以 $\text{inv}[i] \times \text{inv}[r]$：

展开左边：

因为 $i \times \text{inv}[i] \equiv 1$，$r \times \text{inv}[r] \equiv 1$，所以上式变为：

即：

第四步：移项，得到递推公式

在模运算里，负数可以加上 $p$ 变成正数。所以常用写法是：

这里的 $\frac{p}{i}$ 是整数除法（向下取整），在代码里用 p / i（C++）或 p // i（Python）。

特别提醒：需要先知道 $\text{inv}[1] = 1$，因为 $1$ 的逆元就是自己。

手工验证例子

取 $p=7$，计算 $\text{inv}[1]$ 到 $\text{inv}[6]$：

• $i=1$: $\text{inv}[1] = 1$
• $i=2$: $k = 7/2 = 3$，$r = 7\%2 = 1$，$\text{inv}[2] = (7 - 3 \times \text{inv}[1]) \% 7 = (7-3)\%7 = 4$。验证：$2\times4=8\equiv1$。
• $i=3$: $k=2, r=1$，$\text{inv}[3] = (7 - 2\times1)\%7 = 5$，验证：$3\times5=15\equiv1$。
• $i=4$: $k=1, r=3$，$\text{inv}[4] = (7 - 1\times\text{inv}[3])\%7 = (7-5)\%7 = 2$，验证：$4\times2=8\equiv1$。
• $i=5$: $k=1, r=2$，$\text{inv}[5] = (7 - 1\times\text{inv}[2])\%7 = (7-4)\%7 = 3$，验证：$5\times3=15\equiv1$。
• $i=6$: $k=1, r=1$，$\text{inv}[6] = (7 - 1\times1)\%7 = 6$，验证：$6\times6=36\equiv1$。

全部正确！这个递推公式就像多米诺骨牌一样，从 $\text{inv}[1]$ 开始，一个个往后推。

4. 编程实现——把公式变成代码

4.1 C++ 实现

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

// 线性预处理求 1 到 n 模 p 的逆元，p 必须是质数
vector<int> linear_inv(int n, int p) {
    vector<int> 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
        // 注意先取模再取负，最后再模p确保非负
        inv[i] = (long long)(p - (p / i)) * inv[p % i] % p;
        // 另一种写法：inv[i] = (p - (p / i) * inv[p % i] % p) % p;
    }
    return inv;
}

int main() {
    int n = 10, p = 13;      // 测试：模13，求1..10的逆元
    vector<int> inv = linear_inv(n, p);
    for (int i = 1; i <= n; ++i) {
        cout << "inv[" << i << "] = " << inv[i] << endl;
    }
    // 验证：i * inv[i] % p 应该等于1
    cout << "\n验证：" << endl;
    for (int i = 1; i <= n; ++i) {
        cout << i << " * " << inv[i] << " % " << p << " = "
             << (long long)i * inv[i] % p << endl;
    }
    return 0;
}

代码说明：

• 使用 vector<int> 存储结果，下标从1开始。
• 循环从 i=2 到 n，计算 $k = p / i$（整数除法），$r = p \% i$。
• 注意乘法可能溢出，所以用 (long long) 强转。
• 公式中 p - (p/i) 相当于 $- (p/i)$ 模 $p$，然后再乘以 $\text{inv}[r]$，最后再取模。

4.2 Python 实现

def linear_inv(n: int, p: int) -> list:
    """
    线性预处理求 1 到 n 模 p 的逆元（p为质数）
    返回一个列表，索引从0开始，但0号元素无用，1到n存放结果
    """
    inv = [0] * (n + 1)      # 多开一个位置，inv[0]无意义
    inv[1] = 1               # 1的逆元是1
    for i in range(2, n + 1):
        # 递推公式：inv[i] = p - (p // i) * inv[p % i] % p
        # Python中负数的模会自动转为正数，但为了清晰，我们手动处理
        inv[i] = (p - (p // i) * inv[p % i] % p) % p
    return inv

# 测试
n = 10
p = 13
inv = linear_inv(n, p)
for i in range(1, n + 1):
    print(f"inv[{i}] = {inv[i]}")

# 验证
print("\n验证：")
for i in range(1, n + 1):
    print(f"{i} * {inv[i]} % {p} = {(i * inv[i]) % p}")

代码说明：

• 与C++类似，先初始化一个长度为 n+1 的列表。
• Python 整数除法用 //。
• 公式中 (p - (p // i) * inv[p % i] % p) % p 保证了结果在 $0$ 到 $p-1$ 之间。
• 也可以写成 (- (p//i) * inv[p%i]) % p，因为Python的 % 会返回非负余数。

5. 新手容易犯的错误（避坑指南）

1. 忘记初始化 inv[1] = 1
   递推公式必须从 $i=2$ 开始，如果 inv[1] 没有设好，后面的结果全部会错。

2. 循环从 i=1 开始或 i=0 开始
   应该从 i=2 开始，因为 $i=1$ 已经特殊处理。如果从 i=1 开始，$p/1 = p$，$p \% 1 = 0$，而 inv[0] 没有定义或根本不存在。

3. 忘记取模导致负数
   在 C++ 中，-k * inv[r] 可能是负数，一定要加上 p 并取模。正确写法是 (p - (p/i) * inv[p%i] % p) % p 或者 ( (p - (p/i)) * inv[p%i] ) % p。

4. 误以为所有数都有逆元
   对于非质数模，有些数可能没有逆元（比如 $i$ 和 $p$ 不互质）。本递推公式只适用于质数 $p$，且要求 $i < p$，因为当 $i$ 是 $p$ 的倍数时不存在逆元。

5. 整数除法混淆
   在 C++ 中，p/i 是整数除法，但在 Python 中要用 p // i。如果用 / 会得到浮点数，导致错误。

6. 时间复杂度与空间复杂度

• 时间复杂度：$O(n)$，只需要一个从 2 到 n 的循环。
• 空间复杂度：$O(n)$，需要存储 n+1 个整数。

相比单个逆元计算（$O(\log p)$），当 $n$ 很大（比如 $10^7$）且 $p$ 也很大（如 $10^9+7$）时，线性预处理能省下大量时间。这就像你一次性购买一大堆零食比每次只买一包更有效率。

7. 应用场景举例（生活化）

• 组合数取模：计算 $C(n, k) \bmod p$ 时，需要大量阶乘和阶乘的逆元。先用线性预处理求出 1 到 n 每个数的逆元，再乘起来得到阶乘的逆元。比如，你想知道从 10 个同学中选 3 个参加比赛，有多少种选法（结果模 13），就可以用逆元快速计算。

• 分数取模：计算 $\frac{a}{b} \bmod p$ 相当于 $a \times \text{inv}[b] \bmod p$。比如，你要平分 10 块饼干给 7 个朋友，每个朋友能分到多少“模概念”下的数量？用逆元就能算。

• 密码学和哈希：在 RSA 加密算法中，需要大量模逆元运算；在哈希表的设计中也会用到。

8. 完整示例：计算 1 到 10 的逆元并验证

我们已经在上面的代码中给出了完整示例。你可以自己运行一下，看看输出结果是否满足 $i \times \text{inv}[i] \bmod p = 1$。

9. 相关指引

线性预处理逆元是模运算中的经典技巧，它和下面这些知识紧密相关：

• 费马小定理：$a^{p-1} \equiv 1 \pmod{p}$，可用于单个逆元计算（$\text{inv}[a] = a^{p-2} \bmod p$）。
• 扩展欧几里得算法：可以求解 $ax + py = 1$，得到 $x$ 就是逆元。
• 阶乘逆元：有了 1 到 n 的逆元，可以进一步线性求出阶乘的逆元，用于组合数计算。
• 模运算的四则运算：加减乘除在模意义下的规则。

如果你以后遇到“需要频繁求逆元”的问题（比如在组合数学、数论、算法竞赛中），线性预处理就是你的首选工具。记住：公式记牢，代码写好，逆元就能秒速拿到手！

课后小挑战：
请用线性预处理方法，计算模 $p=998244353$ 下 1 到 1000000 的所有逆元，并验证前几个是否正确。（提示：验证时可以用费马小定理计算单个逆元来对比）

记住：数学是编程的好朋友，把公式理解了，代码自然就会写。加油！