请问这个计算a*b%c的函数原理是什么？

Question

def calculate(self, a, b, c): if b == 0:return 1 ans = 1 while b > 0: if b & 1 : ans = ans * a % c a = a * a % c b >>= 1 return ans

Answer 1

首先这是计算a^b%c或者用Python的话说(a**b) %c
原理是 a*b %c == (a%c * b%c) % c
所以 a**b %c == (a**(b/2) %c * a**(b/2) %c * (b -> if b&1 a else 1) % c) % c