快速幂

  |  

摘要: 本文介绍快速幂的算法原理与代码模板

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


在很多算法中,我们都要计算类似于 $a^{n}$ 这样的值。一个一个地乘当然是可以的,但是如果 n 很大的话,我们还可以用快速幂算法来计算。本文我们以一个模板题来介绍快速幂的算法原理、递归和二进制分解这两种实现方式及其对应的代码模板。

之后介绍一下快速幂的常见变种算法,包括模下快速幂、快速乘法、预处理 $p^{n}$,以及一些例题。


快速幂的算法原理

模板题

50. Pow(x, n)

实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn )。

提示:

1
2
3
-100.0 < x < 100.0
-231 <= n <= 231-1
-1e4 <= xn <= 1e4

示例 1:
输入:x = 2.00000, n = 10
输出:1024.00000

示例 2:
输入:x = 2.10000, n = 3
输出:9.26100

示例 3:
输入:x = 2.00000, n = -2
输出:0.25000
解释:2-2 = 1/22 = 1/4 = 0.25

实现方式1: 递归

不求 $a^{n}$ 而是求 $a^{\frac{n}{2}}$, 然后先不求 $a^{\frac{n}{2}}$, 而是先求 $a^{\frac{n}{4}}$…

对以上思路最直接的实现方式是递归, 代码如下:

代码模板 (C++)

1
2
3
4
5
6
7
8
9
10
11
double quickpower(double x, long long n) 
{
if (n == 0)
return 1;
if (n < 0)
return 1 / quickpower(x, -n);
double mid = quickpower(x, n / 2);
if (n & 1)
return mid * mid * x;
return mid * mid;
}

实现方式2: 二进制分解

除了递归之外,还有一个代码实现技巧: 二进制分解, n -> 1, 2, 4, 8, 16, 32. n 可以分解为 2 的幂次的和. 例如 $13 = 8 + 4 + 1$, 求 $a^{13}$ 需要求 $a^{8}, a^{4}, a^{1}$。

可以用变量存 $a^{1}$, $a^{2}$, …, $a^{n - 1}$, 如果当前幂次是 n 需要的, 则加到结果中. 如何判断当前幂次是否需要, 可以用位掩码来决定, 即下面代码中的 if(n & 1)

代码模板 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
int quickpower(int a, int n)
{
// a==0 && n==0 特判
int ans = 1; // n = 0 时候不进循环
while(n)
{
if(n & 1)
ans *= a;
a *= a;
n >>= 1;
}
return ans;
}

快速幂的一些变种

(1) 模下快速幂

当 a, n 很大时候, $a^{n}$ 显然会溢出,此时需要模下快速幂. 模下快速幂的计算方式就是一边相乘,一边取模,它的正确性需要用下面这几个数论公式来推导。

以下代码中, 除了将参与计算的部分加了取模, 其它的部分没有改变。

代码模板 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
using ll = long long;

int quickpower_mod(int a, int n, int mod) // 处理不了n是负数
{
int ans = 1;
while(n)
{
if(n & 1)
ans = ((ll)ans * a) % mod;
a = (ll)a * a % mod;
n >>= 1;
}
return ans % mod;
}

例题

(2) 预处理 $p^{n}$

有时在算法中需要频繁地求 $a^{n}$, a 不变, n 会变化, 例如字符串匹配的前缀哈希算法. 此时可以不用快速幂,而是直接将 $p^{0}$ 到 $p^{n}$ 全都预处理出来。

下面的代码用了 ull 产生溢出相当于对 $2^64$ 取模,也可以在计算过程中手动取模。

代码模板 (C++)

1
2
3
4
5
6
7
// pp[i] := p 的 i 次幂
vector<unsigned long long> pp(n + 1, 0);
pp[0] = 1;
for(int i = 1; i <= n; ++i)
{
pp[i] = pp[i - 1] * p;
}

(3) 快速乘法

有时会遇到两个 long long 相乘再模一个 long long 的问题。

例如考虑这个问题,求 $a^{b} \mod p$,其中 $1 \leq a,b,p \leq 10^{18}$。

解法类似快速幂的思想,将 b 二进制表示,即 $b = c_{k+1}2^{k-1} + … + c_{0}2^{0}$。

若已经求出 $a \times 2^{i-1} \mod p$,则计算$a \times 2^{i} \mod p$ 时,每一步的结果都不超 $2 \times 10^{18}$。

代码模板 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
ll mul(ll a, ll b, ll p)
{
ll ans = 0;
while(b)
{
if(b & 1)
ans = (ans + a) % p;
b >>= 1;
a = (a * 2) % p;
}
return ans;
}

例题


Share