フェルマーの小定理

2022/12/9現在、AtCoderにおけるPyPyのバージョンは7.3.0なので、以下のコードは動かない。

print(pow(2, -1, 1000000007))

powのexp引数に負の数を取れるのはPython3.8以降であって、PyPy(7.3.0)ではCPython3.6の機能しかサポートされていないため。

そこでPyPyでモジュラ逆数を求める際は上記のコードを以下のように書き換えて使う。

print(pow(2, 1000000005, 1000000007))

これは以下の形で知られるフェルマーの小定理を利用したもので、

$a^{p-1} \equiv 1 (\bmod p)$

上の式を変形して、

$a^{p-2} \equiv a^{-1} (\bmod p)$
とすると上のコードで利用した形になる。

なお、 $O(\log p)$ かかるので多用は厳禁。何度もモジュラ逆数を求める際は前計算するテクが別にあるのでそちらをつかうこと。