概略

全自動mod取り機

アルゴリズム

逆元の実装について補足．

$a^{-1} \mod b$ を求めるには $$ax + by = 1$$ を満たす $x$ を求めることが必要である．ここで $$ \left( \begin{array}{ccc} a & 1 & 0 \\ b & 0 & 1 \end{array} \right) \left( \begin{array}{ccc} -1 \\ a \\ b \end{array} \right) = {\bm 0} $$ という自明な式を考える．この式は行基本変形を用いて，次の形に持っていくことが出来る． $$ \left( \begin{array}{ccc} \gcd(a,b) & x & y \\ 0 & u & v \end{array} \right) \left( \begin{array}{ccc} -1 \\ a \\ b \end{array} \right) = {\bm 0} $$ 1行目に注目すると $$ax + by = \gcd(a,b) = 1$$ であるから，行基本変形の間に $ax + by = 1$ を満たす $x$ が求まっている事がわかる．

したがってライブラリ内で行うことは $$ \left( \begin{array}{ccc} a & s & - \\ b & t & - \end{array} \right) $$ を初期値 $(a,b,s,t) = (a,b,1,0)$ として，行基本変形を $b = 0$ になるまで繰り返すだけである．

実装例

ModInt<$p$>$(x)$ := $\mod p$ の演算をサポート
演算子オーバーロード
- 負号-
- 加法++=
- 減法--=
- 乗法**=
- 除法//=
- 等号==!=
- 入出力>><<
pow$(n)$ := $x^n \mod p$
- $O(\log n)$
inverse$()$ := $x$ の逆元を返す
- $x$ と$p$ がフィボナッチ数列の隣接2項であるとき，最悪計算量$O(\log_{\gamma} p)(\gamma = \frac{1+\sqrt{5}}{2})$