modint での切り捨て除法

$\lfloor x/k \rfloor \bmod p$ を計算したい場合

$x$ を $\bmod\ p$ と $\bmod\ k$ の両方で計算をすればよい。

$\lfloor x/k \rfloor = (x-(x \bmod k))/k$ を $\bmod\ p$ で計算すれば良い。

• 参考: ARC167 B

  

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$ の約数である。