线性求逆元

2021年11月24日 阅读数:2
这篇文章主要向大家介绍线性求逆元,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

线性求逆元

当初作洛谷模板题的时候还没发现原来这就是线性求逆元,如今发现了才知道原来这么好用。数组

首先咱们要求 \([1,n]\pmod p\) 的逆元。ui

第一,咱们知道:spa

\[1^{-1}\equiv1\pmod p \]

如今咱们要求 \(i\pmod p\) 的逆元,确定的,咱们能够把 \(p\) 拆分红:模板

\[p=k\times i+r \]

\[\because p\equiv0\pmod p \]

\[\therefore k\times i+r\equiv 0\pmod p \]

咱们分别让两边乘上 \(i^{-1}\)\(r^{-1}\),则:class

\[k\times r^{-1}+i^{-1}\equiv0\pmod p \]

移项:im

\[i^{-1}\equiv-k\times r^{-1}\pmod p \]

按照开始那条式子 \(p=k\times i+r\) 咱们能够得出:di

\[k=\left\lfloor\frac{p}{i}\right\rfloor \]

\[r=p\bmod i \]

\(k=\left\lfloor\frac{p}{i}\right\rfloor\)\(r=p\bmod i\) 代入到 \(i^{-1}\equiv-k\times r^{-1}\pmod p\) 中咱们能够获得:display

\[i^{-1}\equiv-\left\lfloor\frac{p}{i}\right\rfloor\times (p\bmod i)^{-1}\pmod p \]

因为 \((p\bmod i)<i\),因此 \((p\bmod i)^{-1}\) 必然在前面求过,因此咱们能够提早用一个inv数组记录便可。time