Help us understand the problem. What is going on with this article?

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)の引数yexp)は引数zmod)がある場合、非負でなくてはならないと書いてありますが、その記述は3.8のドキュメントでは削除されています。3.8のドキュメントではpow(base, exp, mod)の引数expが負の数のときは、basemodは互いに素でなければならないと書かれており、引数expmodがある場合でも負の数を許容しています。

実際に確かめてみる。

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とそれ以下の相異なる自然数abが与えられます。
次の式の答えを10**9 + 7で割ったあまりを求めなさい。ただし、ab2*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をシンプルに書けるようになって嬉しいです。

keigo0205
通信会社で監視システムの維持管理と開発をしている3年目社員。競技プログラミングが好きです。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした