Python3.8 以降では、逆元のmodが組み込み関数のpowで計算できる。

概要

競技プログラミングでよく使われる逆元の剰余演算ですが、Python3.8以降では組み込み関数のpowを用いて計算できるようになったようです。

これまでは下記の記事のような方法を参考にして、逆元の剰余を求める関数を独自に作る必要がありました。
「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜(Qiita)

Python3.8以降で例えば

38^{-1}\,\,mod\,\,97

を計算したい時は

pow(38, -1, 97)

で計算できるようになります。

公式ドキュメントを確かめる

Python3.7

組み込み関数-pow(x, y[, z])

pow(x, y[, z])
x の y 乗を返します; z があれば、x の y 乗に対する z の剰余を返します
〜中略〜
z がある場合、 x および y は整数型でなければならず、 y は非負でなくてはなりません。

Python3.8

組み込み関数-pow(base, exp[, mod])

pow(base, exp[, mod])
base の exp 乗を返します; mod があれば、base の exp 乗に対する mod の剰余を返します
〜中略〜
For int operands base and exp, if mod is present, mod must also be of integer type and mod must be nonzero. If mod is present and exp is negative, base must be relatively prime to mod. In that case, pow(inv_base, -exp, mod) is returned, where inv_base is an inverse to base modulo mod.

3.7のドキュメントでは`pow(x, y, z)の引数y（exp）は引数z（mod）がある場合、非負でなくてはならないと書いてありますが、その記述は3.8のドキュメントでは削除されています。3.8のドキュメントではpow(base, exp, mod)の引数expが負の数のときは、baseとmodは互いに素でなければならないと書かれており、引数expはmodがある場合でも負の数を許容しています。

実際に確かめてみる。

keigo0205@MacBook-Pro ~ % python --version
Python 3.8.2
keigo0205@MacBook-Pro ~ % python
Python 3.8.2 (default, Mar 24 2020, 11:35:26) 
[Clang 11.0.0 (clang-1100.0.33.17)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> pow(38, -1, 97)
23
>>> 23 * 38 % 97 == 1
True
>>> exit()

keigo0205@MacBook-Pro ~ % python --version
Python 3.7.7
keigo0205@MacBook-Pro ~ % python
Python 3.7.7 (default, Mar 24 2020, 13:42:02) 
[Clang 11.0.0 (clang-1100.0.33.17)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> pow(38, -1, 97)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: pow() 2nd argument cannot be negative when 3rd argument specified
>>> exit()

本当ですね・・・

AtCoderで逆元のmodを使う問題を解いてみる。

ABC159-D - Bouquetを解いてみます。AtCoderのPythonはバージョン3.8.2になります。

問題概要
自然数nとそれ以下の相異なる自然数aとbが与えられます。
次の式の答えを10**9 + 7で割ったあまりを求めなさい。ただし、aとbは2*10**5以下である点に注意せよ。

2^n - 1 - nCa - nCb

解答例

n, a, b = list(map(int, input().split()))
MOD = 10**9 + 7

# 1!からmax(a, b)!までの逆元をMODで割ったあまりと
# nからn-max(a*b)までをかけてMODで割ったあまりを求めます。
fact = {}
fact[n] = n
fact[n - 1] = fact[n] * (n - 1) % MOD

inv_fact = [0] * (max(a, b) + 1)
inv_fact[1] = 1

for i in range(2, max(a, b) + 1):
    fact[n - i] = fact[n - i + 1] * (n - i) % MOD
    inv_fact[i] = inv_fact[i - 1] * pow(i, -1, MOD) % MOD

subtrahend = 1 + fact[n - a + 1] * inv_fact[a] + fact[n - b + 1] * inv_fact[b]
minuend = pow(2, n, MOD)

print((minuend + 2 * MOD - subtrahend) % MOD)

まとめ

Python3.8になって組み込み関数の機能が拡張されていたので紹介しました。定期的に公式ドキュメントは読んだ方がいいですね。

個人的にはわざわざ独自関数を持ってこずに逆元のmodをシンプルに書けるようになって嬉しいです。