快速幂算法详解
快速幂算法详解
EmoryHuang
发布于 2022-10-27 21:18:50
发布于 2022-10-27 21:18:50
快速幂算法详解
前言
首先考虑这么一个问题
对于这个问题，只要写一个简单的循环就能够搞定
// 普通求幂
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;
}本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-05-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录