乘法逆元
逆元定义
若 \(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}\)，则
严禁直接相除：不能直接把两边的数约分！
例如 \(6 \equiv 10 \pmod{4}\)，两边同除以 \(2\) 得 \(3 \equiv 5 \pmod{4}\)，但 \(3 \not\equiv 5 \pmod{4}\)。
当且仅当除数与模数互质时，乘上除数的逆元才等价于“除法”，而这正是逆元的作用。
求解逆元的方式
我直接参考大佬的总结了qwq，点这里~跳转。
下面是一些细节
-
在扩展欧几里得中，得到一组解的\(x\)是负数，通过（\(x \bmod b + b\)）\(\bmod b\)，就能得到给\(x + db\)后的正数解，最后\(x\)属于（\(0\)~\(b-1\)）范围的值，然后代入原方程反解\(y\)。
-
线性递推是求\(1\)~\(n\)范围的逆元，因为它是从小到大推的，\(1\)在mod任何质数下的逆元是\(1\)，\(p \bmod i\)的范围在\(0\)~\(i-1\)小于\(i\)，\(\text{inv}[i] = (p - p / i) * \text{inv}[p \% i] \% p;\) 在取模情况下的运算要保证每个数都是正数，所以对负的向下取整多加一个\(p\)是为了保证正数运算。
-
还有一种递推方式是通过前缀积+费马小定理从后往前推，这便是求阶层逆元的扩展求一般数组逆元。