快速幂(Exponentiation by squaring,平方求幂)是一种简单而有效的小算法,它可以以的时间复杂度计算乘方。快速幂不仅本身非常常见,而且后续很多算法也都会用到快速幂(龟速加也是此思想)。
思想是二分思想:
计算a的n次方,如果n是偶数(不为0),那么就先计算a的n/2次方,然后平方;如果n是奇数,那么就先计算a的n-1次方,再乘上a;递归出口是a的0次方为1。
递归快速幂的思路非常自然,代码也很简单(直接把递归方程翻译成代码即可):
static int quickMi(int a, int k) {
int res = 1;
//a %= mod; //a可能比较大 a*a 可能会爆int直接进行一次取模;有些地方可以加,有些可以不加
while (k != 0) {
//如果是奇数的话
if ((k & 1) != 0) res = res * a % mod;
a = a * a % mod;
k >>= 1;
}
return res;
}