这是一份关于乘法逆元的学习笔记，涵盖了单个数求逆元和线性求逆元的方法、成立条件及复杂度分析。

### 1. 什么是乘法逆元

在模 $p$ 意义下，如果对于整数 $a$，存在一个整数 $x$ 使得：
$a \cdot x \equiv 1 \pmod p$
则称 $x$ 是 $a$ 在模 $p$ 意义下的乘法逆元，通常记作 $a^{-1}$。在程序实现中，逆元可以将除法转化为乘法：$(m / a) \pmod p = (m \cdot a^{-1}) \pmod p$。

### 2. 成立条件

逆元存在的充分必要条件是：$\text{gcd}(a, p) = 1$，即 $a$ 与 $p$ 互质。
* 当 $p$ 是一个大质数（如 $10^9+7$）时，只要 $a$ 不是 $p$ 的倍数，其逆元就一定存在。
* 如果 $a$ 是 $p$ 的倍数（即 $a \equiv 0 \pmod p$），则逆元不存在（类似于 0 不能作除数）。

---

### 3. 单个求逆元的方法

#### 方法一：费马小定理 (Fermat's Little Theorem)
**适用条件**：$p$ 必须是质数，且 $a$ 不是 $p$ 的倍数。
**原理**：根据费马小定理，$a^{p-1} \equiv 1 \pmod p$。
两边同时除以 $a$，得：$a^{p-2} \equiv a^{-1} \pmod p$。
**复杂度**：$O(\log p)$，通过快速幂实现。

C++ 实现代码：
```cpp
long long fast_pow(long long a, long long b, long long p) {
    long long res = 1;
    a %= p;
    while (b > 0) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
long long get_inv_single(long long a, long long p) {
    return fast_pow(a, p - 2, p);
}
```

#### 方法二：扩展欧几里得算法 (ExGCD)
**适用条件**：只要 $\text{gcd}(a, p) = 1$ 即可，$p$ 不一定是质数。
**原理**：求解线性同余方程 $ax \equiv 1 \pmod p$，等价于求解 $ax + py = 1$。
**复杂度**：$O(\log (\min(a, p)))$。

C++ 实现代码：
```cpp
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;
}
long long get_inv_exgcd(long long a, long long p) {
    long long x, y;
    long long d = exgcd(a, p, x, y);
    return d == 1 ? (x % p + p) % p : -1; // -1 表示不存在
}
```

---

### 4. 线性求逆元 (求 $1 \dots n$ 的所有逆元)

**适用条件**：$p$ 是质数且 $n < p$。
**递推公式推导**：
设 $p = k \cdot i + r$，其中 $k = \lfloor p / i \rfloor, r = p \pmod i$。
在模 $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} \equiv -k \cdot r^{-1} \pmod p$
代入 $k$ 和 $r$：
$i^{-1} \equiv -\lfloor p / i \rfloor \cdot (p \pmod i)^{-1} \pmod p$
为了保证结果为正数，公式写为：
$inv[i] = (p - \lfloor p / i \rfloor) \cdot inv[p \pmod i] \pmod p$

**复杂度**：时间 $O(n)$，空间 $O(n)$。

C++ 实现代码：
```cpp
long long inv[MAXN];
void get_all_inv(int n, int p) {
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) {
        inv[i] = (long long)(p - p / i) * inv[p % i] % p;
    }
}
```

---

### 5. 总结与注意事项

* **大质数模数**：对于 $p = 10^9+7$ 或 $p = 998244353$，费马小定理是最常用的单次求法。
* **批量求逆元**：如果你需要频繁用到 $1 \dots 10^6$ 范围内所有数字的逆元（如计算组合数），请务必使用线性求逆元，否则 $O(n \log p)$ 可能会超时。
* **溢出处理**：在乘法运算中，由于 $10^9+7$ 接近 $2^{30}$，两个数相乘会超过 `int` 范围，代码中必须使用 `long long`。
* **0 没有逆元**：在代码中通常从 $i=1$ 开始递推，并人为规定 $inv[1] = 1$。

这是一份关于乘法逆元的学习笔记，涵盖了单个数求逆元和线性求逆元的方法、成立条件及复杂度分析。

1. 什么是乘法逆元

在模 $p$ 意义下，如果对于整数 $a$，存在一个整数 $x$ 使得： $a \cdot x \equiv 1 \pmod p$ 则称 $x$ 是 $a$ 在模 $p$ 意义下的乘法逆元，通常记作 $a^{-1}$。在程序实现中，逆元可以将除法转化为乘法：$(m / a) \pmod p = (m \cdot a^{-1}) \pmod p$。

2. 成立条件

逆元存在的充分必要条件是：$\text{gcd}(a, p) = 1$，即 $a$ 与 $p$ 互质。 * 当 $p$ 是一个大质数（如 $10^9+7$）时，只要 $a$ 不是 $p$ 的倍数，其逆元就一定存在。 * 如果 $a$ 是 $p$ 的倍数（即 $a \equiv 0 \pmod p$），则逆元不存在（类似于 0 不能作除数）。

3. 单个求逆元的方法

方法一：费马小定理 (Fermat's Little Theorem)

适用条件：$p$ 必须是质数，且 $a$ 不是 $p$ 的倍数。原理：根据费马小定理，$a^{p-1} \equiv 1 \pmod p$。两边同时除以 $a$，得：$a^{p-2} \equiv a^{-1} \pmod p$。 复杂度：$O(\log p)$，通过快速幂实现。

C++ 实现代码：

long long fast_pow(long long a, long long b, long long p) {
    long long res = 1;
    a %= p;
    while (b > 0) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
long long get_inv_single(long long a, long long p) {
    return fast_pow(a, p - 2, p);
}

方法二：扩展欧几里得算法 (ExGCD)

适用条件：只要 $\text{gcd}(a, p) = 1$ 即可，$p$ 不一定是质数。原理：求解线性同余方程 $ax \equiv 1 \pmod p$，等价于求解 $ax + py = 1$。 复杂度：$O(\log (\min(a, p)))$。

C++ 实现代码：

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;
}
long long get_inv_exgcd(long long a, long long p) {
    long long x, y;
    long long d = exgcd(a, p, x, y);
    return d == 1 ? (x % p + p) % p : -1; // -1 表示不存在
}

4. 线性求逆元 (求 $1 \dots n$ 的所有逆元)

适用条件：$p$ 是质数且 $n < p$。 递推公式推导：设 $p = k \cdot i + r$，其中 $k = \lfloor p / i \rfloor, r = p \pmod i$。在模 $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} \equiv -k \cdot r^{-1} \pmod p$ 代入 $k$ 和 $r$： $i^{-1} \equiv -\lfloor p / i \rfloor \cdot (p \pmod i)^{-1} \pmod p$ 为了保证结果为正数，公式写为： $inv[i] = (p - \lfloor p / i \rfloor) \cdot inv[p \pmod i] \pmod p$

复杂度：时间 $O(n)$，空间 $O(n)$。

C++ 实现代码：

long long inv[MAXN];
void get_all_inv(int n, int p) {
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) {
        inv[i] = (long long)(p - p / i) * inv[p % i] % p;
    }
}

5. 总结与注意事项

大质数模数：对于 $p = 10^9+7$ 或 $p = 998244353$，费马小定理是最常用的单次求法。
批量求逆元：如果你需要频繁用到 $1 \dots 10^6$ 范围内所有数字的逆元（如计算组合数），请务必使用线性求逆元，否则 $O(n \log p)$ 可能会超时。
溢出处理：在乘法运算中，由于 $10^9+7$ 接近 $2^{30}$，两个数相乘会超过 int 范围，代码中必须使用 long long。
0 没有逆元：在代码中通常从 $i=1$ 开始递推，并人为规定 $inv[1] = 1$。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com