快速幂算法详解

本文最后更新于:5 个月前

快速幂算法详解

前言

首先考虑这么一个问题

给定三个正整数 a, b, m(a < $10^9$,b < $10^9$,1 < m < $10^9$),求 $a^b$ % m。

对于这个问题,只要写一个简单的循环就能够搞定

1
2
3
4
5
6
7
8
// 普通求幂
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 的处理,我们很容易得到如下事实:

若 b 为奇数,则$a^b=a\times a^{b-1}$

若 b 为偶数,则$a^b=a^{b/2}\times a^{b/2}$

举个例子,求 $2^7$:

  1. 由于 7 为奇数,因此有 $2^7 = 2 \times 2^6$
  2. 由于 6 为偶数,因此有 $2^6$ = $2^3 \times 2^3$
  3. 由于 3 为奇数,因此有 $2^3$ = $2 \times 2^2$
  4. 由于 2 为偶数,因此有 $2^2$ = $2^1 \times 2^1$
  5. 由于 1 为奇数,因此有 $2^1$ = $2 \times 2^0$
  6. 最后 $2^0=1$,然后从下往上计算即可

根据上面的方程,很容易通过二分的思想得到快速幂算法的递归版本

1
2
3
4
5
6
7
8
9
10
// 快速幂,递归写法
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;
}
}

迭代快速幂

下面说明一下快速幂的迭代写法

同样的,主要还是在指数 b 的处理,以 $2^{10}$ 为例

可以发现,$2^{10}$ 可以表示为 $2^8$ 和 $2^2$ 的乘积。

同样的对 $a^b$ 进行推广,我们可以把 $a^b$ 表示成 $a^{2^{k}}$,$a^{2^{k-1}}$,…,$a^8$,$a^4$,$a^2$,$a^1$中若干项的乘积,即:

具体来说,枚举指数 b 的每一位,若当前位为 1,则结果累计 $a^{2^{i}}$

举例如下

a n(binary) ans
2(1)2 1010 1
2(10)2 101 2(10)2
2(100)2 10 2(10)2
2(1000)2 1 2(10)2 * 2(1000)2

具体代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
// 快速幂,迭代写法
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;
}

本文作者: EmoryHuang
本文链接: https://emoryhuang.cn/blog/1504958816.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明来自EmoryHuang