逆元
python3.8以降は以下のように書ける。
code: modinv.py
inv_a = pow(a, -1, mod)
ただし2022/8現在AtCoderでの対応バージョンは
Python (3.8.2)
PyPy3 (7.3.0) = Python 3.6
となっているため、上記のコードはPythonでは通りPyPyではREとなる。
PyPyの場合は
フェルマーの小定理
を用いて以下のように書くことで通る。
code: modinv.py
inv_a = pow(a, mod-2, mod)