読者です 読者をやめる 読者になる 読者になる

逆元の列挙

takapt0226.hatenablog.com

上の記事の数式が壊れてて式を追うのに時間がかったから、忘れないようにメモ

 m = (m / i) \cdot i + m \% i

 \mod m (-m / i) \cdot i ≡ m \% i

 (m \% i)^{-1} をかけて
 (-m / i) \cdot i \cdot (m \% i)^{-1}≡1

 i^{-1} をかけて
 (-m / i) \cdot (m \% i)^{-1}≡i^{-1}
 i^{-1}≡(m - m / i) \cdot (m \% i)^{-1}

gist.github.com