Dans Python3.8 et versions ultérieures, le mod inverse peut être calculé avec la fonction intégrée pow.

Aperçu

C'est une opération de reste inverse qui est souvent utilisée dans la programmation de compétition, mais il semble qu'elle puisse être calculée à l'aide de la fonction intégrée pow dans Python 3.8 ou version ultérieure.

Jusqu'à présent, il fallait créer sa propre fonction pour trouver le reste de l'élément inverse en se référant à la méthode décrite dans l'article suivant. Une fonction spéciale sur la façon de trouver "trop divisé par 1000000007"! ~ De l'élément inverse au logarithme discret ~ (Qiita)

Par exemple en Python 3.8 ou version ultérieure

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

Quand tu veux calculer

pow(38, -1, 97)

Vous pourrez calculer avec.

Consultez la documentation officielle

Python3.7 Fonctions intégrées-pow (x, y [, z])

pow(x, y[, z]) Renvoie la puissance y-ième de x; si z existe, renvoie le reste de z pour la puissance y-ième de x ~ Omis ~ S'il y a> z, x et y doivent être de type entier et y doit être non négatif.

Python3.8 Fonctions intégrées-pow (base, exp [, mod])

pow(base, exp[, mod]) Renvoie la puissance étendue de la base; s'il y a un mod, renvoie le reste du mod pour la puissance étendue de la base ~ Omis ~ 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.

La documentation 3.7 indique que `` l'argument pow (x, y, z) y (ʻexp) doit être non négatif s'il y a un argument z ( mod). , Cette description a été supprimée dans la documentation 3.8. La documentation 3.8 indique que lorsque l'argument pow (base, exp, mod) exp est un nombre négatif, base et mod doivent être premiers l'un par rapport à l'autre, et l'argument ʻexp ʻAutorise les nombres négatifs même avec mod.

Je vais vraiment le vérifier.

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()

C'est vrai···

Essayez de résoudre le problème de l'utilisation du mod inversé avec AtCoder.

Résolvons ABC159-D --Bouquet. Le Python d'AtCoder est la version 3.8.2.

Résumé du problème Étant donné les nombres naturels «n» et les différents nombres naturels «a» et «b» en dessous. Trouvez la réponse de la formule suivante divisée par «10 ** 9 + 7». Cependant, notez que «a» et «b» sont inférieurs ou égaux à «2 * 10 ** 5».

2^n - 1 - nCa - nCb

Exemple de réponse

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

# 1!À partir de max(a, b)!L'élément inverse jusqu'à est divisé par MOD
#n à n-max(a*b)Divisez par MOD pour trouver le reste.
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)

Résumé

Je l'ai introduit car la fonction de la fonction intégrée a été étendue dans Python 3.8. Vous devriez lire régulièrement la documentation officielle.

Personnellement, je suis heureux de pouvoir écrire simplement le mod inversé sans avoir à apporter ma propre fonction.