乘法逆元、组合数取模刷题总结

乘法逆元

逆元定义

若 \(a \times x \equiv 1 \pmod{b}\)，且 \(a\) 与 \(b\)​ 互质，那么我们就能定义:
\(x\) 为 \(a\) 的逆元，记为 \(a^{-1}\)，所以我们也可以称 \(x\) 为 \(a\) 在 \(\bmod\ b\)​​​ 意义下的倒数。

为什么要满足 \(a\) 与 \(b\) 互质？

同余方程 \(a \times x \equiv 1 \pmod{b}\) 等价于不定方程：\(a \cdot x + b \cdot y = c \quad (\text{这里 } c = 1)\) 根据扩展欧几里得定理

这个方程有整数解的条件是：\(c \mid \gcd(a, b)\)，即 \(1 \mid \gcd(a, b)\)，这等价于 \(\gcd(a, b) = 1\)。

所以 \(a\) 与 \(b\) 必须互质。

同余的基本性质

同余符号 \(\equiv\) 在很多运算上和等号 \(=\) 很像，可以进行加减法和乘法。若 \(a \equiv b \pmod{m}\)，\(c \equiv d \pmod{m}\)，则

\[a \pm c \equiv b \pm d \pmod{m} \]

\[a \times c \equiv b \times d \pmod{m} \]

严禁直接相除：不能直接把两边的数约分！

例如 \(6 \equiv 10 \pmod{4}\)，两边同除以 \(2\) 得 \(3 \equiv 5 \pmod{4}\)，但 \(3 \not\equiv 5 \pmod{4}\)​​​。

当且仅当除数与模数互质时，乘上除数的逆元才等价于“除法”，而这正是逆元的作用。

求解逆元的方式

我直接参考大佬的总结了qwq，点这里~跳转。
下面是一些细节

1. 在扩展欧几里得中，得到一组解的\(x\)是负数，通过（\(x \bmod b + b\)）\(\bmod b\)，就能得到给\(x + db\)后的正数解，最后\(x\)属于（\(0\)~\(b-1\)）范围的值，然后代入原方程反解\(y\)。

2. 线性递推是求\(1\)~\(n\)范围的逆元，因为它是从小到大推的，\(1\)在mod任何质数下的逆元是\(1\)，\(p \bmod i\)的范围在\(0\)~\(i-1\)小于\(i\)，\(\text{inv}[i] = (p - p / i) * \text{inv}[p \% i] \% p;\) 在取模情况下的运算要保证每个数都是正数，所以对负的向下取整多加一个\(p\)是为了保证正数运算。

3. 还有一种递推方式是通过前缀积+费马小定理从后往前推，这便是求阶层逆元的扩展求一般数组逆元。