引入
快速幂，顾名思义，就是快速算底数的n次幂。其时间复杂度为 O(logn)， 与朴素的O(n)相比效率有了极大的提高，在算法竞赛中有着广泛的运用。
推导前提
明确一下取模运算的性质：
- (a + b) % c = (a % c + b % c) % c
-
(a - b) % c = (a % c - b % c + c) % c
- (a * b) % c = (a * c + b * c) % c
以及幂次方运算的方法（指数相加相减相乘相除）
推导过程
已知a、b，求a的b次方的值，结果模c（a、b、c均小于int最大范围）
很明显，直接运算不仅会爆int，还会爆时间。所以可以用分治的思想，像这样（假设b为偶数）
a^b = a^(b/2) * a^(b/2)
如果需要模的话，可以根据模运算的性质变为：
a^b%c = a^(b/2)%c * a^(b/2)%c
那么，a^(b/2)仍然可以继续分成a^(b/2/2)，a^(b/2/2)还能分成a^(b/2/2/2)……直到b的值为1为止
如果b为奇数，可以先提出一个a，再去乘就行了
a^b = a^(b/2) * a^(b/2) * a
时间复杂度分析
无论使用cmath中的pow()还是手写循环，假设指数为b，时间复杂度都是O(b)。若采用快速幂的方法，每次除以二，时间复杂度下降到了O(logb)，优化的非常大，而且也可以解决结果取模的需要。
代码实现
递归写法
1
2
3
4
5
6
7
8
9
10
11
12
int quickpow(int a, int b, int c) { // 返回(a^b) % c O(logn)
if(b == 1) return a % c;
if(b % 2 == 0) {
int ret = quickpow(a, b/2, c);
return ret * ret % c;
} else {
int ret = quickpow(a, b/2, c);
ret = ret * ret % c;
ret = ret * a % c;
return ret;
}
}
循环写法
1
2
3
4
5
6
7
8
9
int quickpow(int a, int b, int n) {
int ret = 1;
while(b) {
if(b % 2 == 1) ret = ret * a % n;
a = a*a%n;
b = b/2;
}
return ret;
}
总结
快速幂算法可以理解为采用了类分治的思想，将一个大问题转化为了多个完全相同的小问题，经过logn次便能够解决问题，是一个非常优秀的算法。其实快速幂还可以采用位运算的方法将常数卡得更优秀，这里旨在便于理解，就不写了。
CSP-J2021rp++！！！
