modint での切り捨て除法

modint の高速逆元計算

• $p = qa + r$ とする（商と余り）。$\bmod\ p$$a^{-1} = -qr^{-1}$ である。
  • 証明: $\bmod\ p$ で $qa + r = 0$ なので、$a^{-1} = -qr^{-1}$ と求まる。
• つまり、逆元に関して inv[a] = -inv[mod % a] * (mod / a ) という漸化式が立つ

よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方 - けんちょんの競プロ精進記録

modint における位数

modint の位数の理論

$\varphi$ をオイラーのトーシェント関数とする

$(\mathbb{Z}/n\mathbb{Z})^{\times}$ の元の位数は $\varphi(n)$ の約数である。

特に、$p$ を素数としたとき、$(\mathbb{Z}/p\mathbb{Z})^{\times}$ の元の位数は $p-1$ の約数である。

証明: ラグランジュの定理から言える。

$p$ を素数とする。$(\mathbb{Z}/p\mathbb{Z})^{\times}$ の位数 $k$ の元の数は $k \mid p-1$ のとき $\varphi(k)$ である。