pow 是 Python 的内置函数，用来进行幂运行：

>>> help(pow)
pow(base, exp, mod=None)
    Equivalent to base**exp with 2 arguments or base**exp % mod with 3 arguments
    ...
>>> pow(5, 3)
125

从 Python 3.8 版本开始，在同样的接口下，增加了计算逆元的功能：

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.

Here’s an example of computing an inverse for 38 modulo 97:

>>> pow(38, -1, mod=97)
23
>>> 23 * 38 % 97 == 1
True

什么是乘法逆元

如果 ax ≡ 1 (mod b)，则称 x 为 a mod b 的逆元，记作 a^-1，所以 a a^-1 ≡ 1 (mod b) 。

比如上面的 23 和 38 关于模 97 互为逆元。

参考资料

• https://docs.python.org/3/library/functions.html#pow
• 乘法逆元 https://oi-wiki.org/math/number-theory/inverse/
• 中国剩余定理 https://oi-wiki.org/math/number-theory/crt/

# Tagged as python ·