Python实现快速幂取模

网上关于python实现算法的题很少，协会又叫自己写一写新生赛题解，我就来试一试，走上这条不归路。 显然，这个题大佬来写题解：“水题，下一个”
但是，我们还是来看一看。
首先，看到999999999就知道这个题直接杠肯定TLE，所以我们用快速幂取模。快速幂是什么？就是a^b = (a*a)^(b/2)。
取模还要用到一个公式

(ab)%c = [(a%c)(b%c)]%c
以下为证明
a % c = d --> a = tc + d
b % c = e --> b = kc + e
(ab) % c = (tc + d)(kc + e) % c
= (tkc^2+(te+dk)c+de)%c
= (de) % c = [(a%c)*(b%c)]%c

再来看代码 def quick_algorithm(a,b,c): a=a%c ans=1 while b!=0: if b&1: ans=(ans*a)%c b>>=1 a=(a*a)%c return ans T = int(input()) lst = [] for i in range(T): a,b = list(map(int,input().split())) lst.append(quick_algorithm(a,b,pow(10,9)+7)) for i in lst: print(i) 最后解释一下b>>=n,相当于把b除以2的n次方，并向下取整。