【数论】逆元
若 \(b, m\) 互质，并且 \(b | a\)，则存在一个整数 \(x\) 使得 \(\dfrac{a}{b} \equiv a \times x \ (\bmod m)\)。则称 \(x\) 为 \(b\) 的模 \(m\) 乘法逆元，记作 \(b^{-1}(\bmod m)\)。
就例如 \(b=31, m=5, a=93\)，就存在 \(x=1\) 满足 \(\dfrac{93}{31} \equiv 93 \times 1 \ (\bmod 5)\)。
因为乘法满足模，即 \((a \times b) \bmod m = (a \bmod m) \times (b \bmod m)\)；
而除法不满足，故乘法逆元就可以很好地解决这个问题，即 \(\dfrac{a}{b} \bmod m=((a \bmod m) \times (b^{-1} \bmod m)) \bmod m\)。
这里介绍三种求逆元的方法：
因为 \(\dfrac{a}{b}\equiv a \times b^{-1} \equiv \dfrac{a}{b} \times b \times b^{-1} \ (\bmod m)\)，所以 \(b * b^{-1} \equiv 1 (\bmod m)\)。
其实也就是要找到一个 \(x\)，满足 \(b \times x \equiv 1 (\bmod m)\)。
当 \(m\) 为质数时，根据费马小定理 \(b^p \equiv b \ (\bmod m)\) 可得：\(b \times b^{p-2} \equiv 1 \ (\bmod m)\)。
因此，当模数 \(m\) 为质数时，\(b^{m-2}\) 就是 \(b\) 的模 \(m\) 乘法逆元。
第一种方法说过，
其实也就是要找到一个 \(x\)，满足 \(b \times x \equiv 1 (\bmod m)\)。
故我们可以使用扩展欧几里得来求解 \(x\)。
这里介绍一个线性求 \(1 \sim n\) 在模 \(m\) 的逆元。
我们设 \(m = q \times d + r ~ (r < d)\)。
可以得到；
- \(q \times d + r \equiv 0 \ (\bmod \ m)\)，
- \(q=\left\lfloor\dfrac{m}{d}\right\rfloor\)
- \(m \ \bmod d = (q \times d + r) \ \bmod \ d = r\) 故 \(r = m \ \bmod \ d\)。
对于式子 \(1\) 两边同乘 \(d^{-1} \times r^{-1}\)，
得到 \(q \times r^{-1} + d^{-1} \equiv 0 \ (\bmod \ m)\)。
\(d^{-1} \equiv -q \times r^{-1} \ (\bmod \ m)\)。
\(d^{-1} \equiv -\left\lfloor\dfrac{m}{d}\right\rfloor \times (m \ \bmod d) ^ {-1} \ (\bmod \ m)\)
根据前面的 \((m \ \bmod d) ^ {-1}\) 推出后面的 \(d^{-1}\)。
code
冲冲冲