逆元
模意义下的倒数 ——IIIIIlIIIl
线性递推¶
求 \(i^{-1}\)，我们令 \(k = \lfloor \frac{p}{i} \rfloor\)（商）；\(j = p \bmod i\)（余数）。有：
\[
p = ki + j
\]
再放到 \(\mod p\) 意义下就会得到 \(ki+j \equiv 0 \pmod p\)，两边同时乘 \(i^{-1} \times j^{-1}\)：
\[
kj^{-1}+i^{-1} \equiv 0 \pmod p
\]
\[
i^{-1} \equiv -kj^{-1} \pmod p
\]
再带入 \(j = p \bmod i,k = \lfloor \frac{p}{i} \rfloor\)：
\[
i^{-1} \equiv -\lfloor\frac{p}{i}\rfloor (p \bmod i)^{-1} \pmod p
\]
我们注意到 \(p \bmod i < i\)，已经知道了小于\(i\)的所有模 \(p\) 下的逆元。
1 | |
费马小定理¶
注意：p为质数，且a不为p的倍数，否则模意义下为0，没有逆元。
exgcd¶
ax=1 (mod p)
ax+py=1
x即为a的逆元