首先考虑这么一个问题
对于这个问题,只要写一个简单的循环就能够搞定
// 普通求幂
long long QuickPow(long long a, long long b, long long m) {
long long ans = 1;
for (int i = 0; i < b; i++) {
ans = ans * a % m;
}
return ans;
}
然而,当 a, b 到达一定值时,最终的结果会非常大,对于这个问题,O(b)的时间复杂度很难进行。
快速幂,就是用效率更高(时间复杂度更低)的方法求幂,可以将时间复杂度优化至 O(logn)
快速幂算法的关键在于对指数 b 的处理,我们很容易得到如下事实:
根据上面的方程,很容易通过二分的思想得到快速幂算法的递归版本
// 快速幂,递归写法
long long QuickPow(long long a, long long b, long long m) {
if (b == 0) return 1;
if (b % 2 == 1) // 如果 b 为奇数,转化为 b - 1
return a * QuickPow(a, b - 1, m) % m;
else { // 如果 b 为偶数,转化为 b / 2
long long mul = QuickPow(a, b / 2, m);
return mul * mul % m;
}
}
下面说明一下快速幂的迭代写法
举例如下
具体代码实现如下:
// 快速幂,迭代写法
long long QuickPow(long long a, long long b, long long m) {
long long ans = 1;
while (b > 0) {
if (b & 1) { // 若 b 的二进制末尾为 1(也可以写成 if(b % 2))
ans = ans * a % m; // ans 累加上 a
}
a = a * a % m; // a取平方
b >>= 1; // b 的二进制右移一位(也可以写成 b /= 2)
}
return ans;
}