### 1. 逆元存在性的判别
在笔记中可以加上这一句核心：
> $b$ 在模 $m$ 意义下存在逆元的充要条件是 $\gcd(b, m) = 1$。
> 如果 $\gcd(b, m) \neq 1$，则除法 $a/b \pmod m$ 不能直接通过乘逆元来计算。

### 2. 补充：阶乘逆元的线性递推
在计算组合数 $C_n^m = \frac{n!}{m!(n-m)!}$ 时，我们需要频繁用到阶乘的逆元。如果对每个数都用 ExGCD 求逆元，效率太低。

**技巧：**
1. 先计算 $n! \pmod P$。
2. 用快速幂/ExGCD 求出 $inv[n!] = (n!)^{-1} \pmod P$。
3. **逆向递推**：因为 $((i-1)! )^{-1} = (i!)^{-1} \times i \pmod P$。

```cpp
// 预处理阶乘逆元
void init_fact_inv(int n, int P) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % P;
    
    inv_fact[n] = quick_pow(fact[n], P - 2, P); // 费马小定理
    for (int i = n - 1; i >= 0; i--) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % P;
    }
}
```
*这个技巧能让你在 $O(n)$ 预处理后，$O(1)$ 时间内求出任何组合数。*

---

### 3. 关于“没有逆元时”的深度解析 (10.2 补充)

你提到的公式 $\frac{a}{b} \pmod m = \frac{a \pmod{bm}}{b}$ 是非常精妙的。

**公式：**
$$\frac{a}{b} \bmod m = \frac{a \bmod (bm)}{b}$$

**适用场景：**
当 $b$ 和 $m$ 不互质（即 $\gcd(b, m) > 1$）时，传统的逆元失效。只要 $bm$ 不溢出（在 `long long` 范围内），这个公式是救命稻草。

**另一个常用技巧（约分法）：**
如果我们要算 $\frac{a}{b} \pmod m$，但 $\gcd(b, m) = d > 1$：
1. 观察发现，如果 $a/b$ 是整数，那么 $a$ 必然也是 $d$ 的倍数。
2. 我们可以同时缩小分子、分母和模数：
   $$\frac{a}{b} \bmod m = \left( \frac{a/d}{b/d} \bmod \frac{m}{d} \right)$$
   （虽然这在某些情况下并不常用，但在推导数论公式时很有用）。

---

### 4. 离线批量求任意 $n$ 个数的逆元
如果你现在有 $n$ 个**不连续**的数 $a_1, a_2, \dots, a_n$，想求它们的逆元，有没有比 $O(n \log P)$ 更快的方法？
有，利用**前缀积**可以 $O(n + \log P)$ 解决：

1. 计算前缀积 $s_i = a_1 \times a_2 \times \dots \times a_i$。
2. 求出最后一个前缀积的逆元 $sv_n = s_n^{-1}$。
3. 逆向计算前缀积逆元：$sv_{i-1} = sv_i \times a_i$。
4. 则单个元素的逆元 $inv[a_i] = sv_i \times s_{i-1}$。

---

### 总结你的笔记逻辑优化

你的笔记现在非常完整，这套组合数学与数论的工具包足以应对大多数算法竞赛中的取模计算问题！

1. 逆元存在性的判别

在笔记中可以加上这一句核心：

$b$ 在模 $m$ 意义下存在逆元的充要条件是 $\gcd(b, m) = 1$。如果 $\gcd(b, m) \neq 1$，则除法 $a/b \pmod m$ 不能直接通过乘逆元来计算。

2. 补充：阶乘逆元的线性递推

在计算组合数 $C_n^m = \frac{n!}{m!(n-m)!}$ 时，我们需要频繁用到阶乘的逆元。如果对每个数都用 ExGCD 求逆元，效率太低。

技巧： 1. 先计算 $n! \pmod P$。 2. 用快速幂/ExGCD 求出 $inv[n!] = (n!)^{-1} \pmod P$。 3. 逆向递推：因为 $((i-1)! )^{-1} = (i!)^{-1} \times i \pmod P$。

// 预处理阶乘逆元
void init_fact_inv(int n, int P) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % P;

    inv_fact[n] = quick_pow(fact[n], P - 2, P); // 费马小定理
    for (int i = n - 1; i >= 0; i--) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % P;
    }
}

这个技巧能让你在 $O(n)$ 预处理后，$O(1)$ 时间内求出任何组合数。

3. 关于“没有逆元时”的深度解析 (10.2 补充)

你提到的公式 $\frac{a}{b} \pmod m = \frac{a \pmod{bm}}{b}$ 是非常精妙的。

公式： $$\frac{a}{b} \bmod m = \frac{a \bmod (bm)}{b}$$

适用场景： 当 $b$ 和 $m$ 不互质（即 $\gcd(b, m) > 1$）时，传统的逆元失效。只要 $bm$ 不溢出（在 long long 范围内），这个公式是救命稻草。

另一个常用技巧（约分法）： 如果我们要算 $\frac{a}{b} \pmod m$，但 $\gcd(b, m) = d > 1$： 1. 观察发现，如果 $a/b$ 是整数，那么 $a$ 必然也是 $d$ 的倍数。 2. 我们可以同时缩小分子、分母和模数： $$\frac{a}{b} \bmod m = \left( \frac{a/d}{b/d} \bmod \frac{m}{d} \right)$$ （虽然这在某些情况下并不常用，但在推导数论公式时很有用）。

4. 离线批量求任意 $n$ 个数的逆元

如果你现在有 $n$ 个不连续的数 $a_1, a_2, \dots, a_n$，想求它们的逆元，有没有比 $O(n \log P)$ 更快的方法？有，利用前缀积可以 $O(n + \log P)$ 解决：

计算前缀积 $s_i = a_1 \times a_2 \times \dots \times a_i$。
求出最后一个前缀积的逆元 $sv_n = s_n^{-1}$。
逆向计算前缀积逆元：$sv_{i-1} = sv_i \times a_i$。
则单个元素的逆元 $inv[a_i] = sv_i \times s_{i-1}$。

总结你的笔记逻辑优化

方法	复杂度	限制条件	备注
费马小定理	$O(\log P)$	$P$ 必须是质数	最常用
扩展欧几里得	$O(\log P)$	$\gcd(b, P)=1$	$P$ 不是质数时用
线性递推	$O(n)$	$P$ 必须是质数	求 $1 \dots n$ 所有逆元
阶乘逆元递推	$O(n)$	$P$ 必须是质数	高频用于组合数
变模数除法	$O(1)$	$bm$ 不溢出	无法求逆元时的绝招