競プロ用ライブラリを作る Advent Calendar 2024の6日目です.
ModIntって?
競プロでよく出題される「$998244353$で割ったあまり」みたいな問題形式で楽に計算するための型です.
ここでは32bitの静的に法が決まっているModIntを実装します.
仕組み
頑張って演算子オーバーロードをします.
以下, MODの数を$M$と置きます. $998244353$とかの数です.
除算
除算は$M$が合成数でも大丈夫なように, オイラーの定理というのを使います.
オイラーの定理は何かしらの整数$a$が$M$と互いに素なとき
a^{\varphi(M)} \equiv 1 \mod M
が成り立つ, というやつです. ここで$\varphi(M)$は「$1$以上$M$未満で$M$と互いに素な整数の個数」です. これをコンパイル時に計算できるようにconst fnで実装します.
φ関数
$\varphi(M)$の値は$M$を素因数分解した結果から計算できます.
$M$を素因数分解した結果を
M=\prod_{i=1}^N p_i^{r_i} = p_1^{r_1}p_2^{r_2}p_3^{r_3}...p_n^{r_n}
と書けるとき (ただし, 異なる$i,j$について$p_i\ne p_j$と, 任意の$i$について$r_i\ne 0$が成り立つ)
\varphi(M) = \prod_{i=1}^N (p_i-1)p_i^{r_i - 1}
と計算できます. 実装するのは32bitのModIntなので試し割り法でも十分速いです.
実装
Rustには定数ジェネリクスがあるのでそこに$M$の値を渡せる実装にしました.
$M$の値に応じてu32とu64を切り替える, みたいなこともしたかったんですが, Rustだと厳しそうです. こういうときにC++の優位性が出てきますね.
演算子のオーバーロードは全部ちゃんと書いてるとすごい量になるのでマクロを使って効率的に行いましょう.
まとめ
いかがでしたか?
明日は同じくMoから始まる名前のものを実装します.