Python 3.8 pow can now take a negative value for the second argument, even if you specify the third argument, which is also noted in the Python 3.8 release notes.
What’s New In Python 3.8: Other Language Changes
For integers, the three-argument form of the pow() function now permits the exponent to be negative in the case where the base is relatively prime to the modulus.
And it seems that it is much faster to calculate the inverse element by specifying -1.
$ python3.8
Python 3.8.3 (default, May 23 2020, 15:50:53)
[GCC 9.3.0] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from timeit import timeit
>>> m = 1000000007
>>> pow(2, m - 2, m)
500000004
>>> pow(2, -1, m)
500000004
>>> timeit(lambda: [pow(i, m - 2, m) for i in range(1, 10000)], number=100)
3.5805746999103576
>>> timeit(lambda: [pow(i, -1, m) for i in range(1, 10000)], number=100)
1.2788116000592709
Recommended Posts