odan’s diary

逆元の列挙

<a href="http://takapt0226.hatenablog.com/entry/2013/03/15/213551">1~nまでの逆元をO(n)で求める方法 - takapt0226's diary</a>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