快速幂算法

问题：如何快速计算 xnx^n，x−nx^{-n}？

提示：

x−n=(1x)nx^{-n} = (\frac{1}{x})^n

算法实现

快速幂，二进制取幂（Binary Exponentiation，也称平方法）是一个在 O(log⁡n)O(\log n) 时间内计算 xnx^n 的技巧性算法。快速幂算法的本质是分治算法。

递归版本

这个版本能直观理解计算过程。

1
2
3
4
5
6
7
8
9
// 计算x的n次方，x可能为负数
Pow(x, n):
	return n >= 0 ? QUICK-MUL(n,x) : 1.0 / QUICK-MUL(-n,x)

QUICK-MUL(N,x)
	if N == 0:
		return 1.0
	y = QUICK-MUL(N / 2 ,x) // 这里是整除，存在向下取整的过程
	return N % 2 == 0 ? y * y : y * y * x

复杂度分析：

  • 时间复杂度：O(log⁡n)O(\log n)，即为递归的层数。
  • 空间复杂度：O(log⁡n)O(\log n)，即为递归的层数。这是由于递归的函数调用会使用栈空间。

迭代版本

假设要计算 x9x^9：

image.png

形式化来讲：

n=2i0+2i1+⋯+2ikxn=x2i0×x2i1×⋯×x2ik\begin{aligned} n&=2^{i_{0}}+2^{i_{1}}+\dots+2^{i_{k}} \\ x^n&=x^{2^{i_{0}}}\times x^{2^{i_{1}}}\times\dots \times x^{2^{i_{k}}} \end{aligned}

因此算法可以这样写，把 n 看成一个二进制数，从 n 的低位开始依次检查二进制位，如果为 1，则把当前 x 乘到结果中。每次检查下一位时，x 自身翻一番。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def quickMul(N):
	ans = 1.0
	# 贡献的初始值为 x
	x_contribute = x
	# 在对 N 进行二进制拆分的同时计算答案
	while N > 0:
		if N % 2 == 1:
			# 如果 N 二进制表示的最低位为 1，那么需要计入贡献
			ans *= x_contribute
		# 将贡献不断地平方
		x_contribute *= x_contribute
		# 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
		N //= 2
	return ans

复杂度分析：

  • 时间复杂度：O(log⁡n)O(\log n)，即为对 n 进行二进制拆分的时间复杂度。
  • 空间复杂度：O(1)O(1)。

快速幂的应用

模指数运算（模意义下的取幂）

分配律：m 是正整数且 a 和 b 是整数，那么有

  • (a+b) mod m=((a mod m)+(b mod m)) mod m(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m
  • a⋅b mod m=((a mod m)(b mod m)) mod ma\cdot b \bmod m = ((a \bmod m)(b \bmod m)) \bmod m

这个定理其实也解释了为什么在一些算法题中，当题目要求给出最终计算结果取模时，即便我们在过程中取模也不会出错的原因。

假设我们要计算 bn mod mb^n \bmod m，其中 n 是一个二进制表示的数：

n=(ak−1ak−1…a1a0)2bn=bak−1⋅2k−1+⋯+a1⋅21+a0=bak−1⋅2k−1⋯a0\begin{aligned} n&=(a_{k-1}a_{k-1}\dots a_{1}a_{0})_{2} \\ b^n &= b^{a_{k-1}\cdot 2^{k-1}+\dots+a_{1}\cdot 2^{1}+a_{0}} = b^{a_{k-1}\cdot 2^{k-1}}\dotsb^{a_{0}} \end{aligned}

  • 需求出 b,b2,…,b2k−1b,b^2,\dots,b^{2^{k-1}}，再把 aj=1a_{j}=1 的那些项相乘。
  • 为了提高效率并减少空间需求，每乘一项后，都做一次模 m 运算以缩小结果值。
1
2
3
4
5
6
7
8
MODULAR-EXPONENTIATION(b: int, n: 二进制数 ,m: 正整数)
	x=1
	power = b % m
	for i=0 to k-1
		if n[i]==1
			x = (x*power) % m
		power = (power*power) % m
	return x

此外，我们还可以使用费马小定理加速算法过程。

费马小定理：如果 p 是素数，a 是不能被 p 整除的整数，那么 ap−1≡1( mod p)a^{p-1} ≡ 1 (\bmod p)，而且对每个整数 a 都有 ap≡a( mod p)a^p ≡ a (\bmod p)

例子：利用费马小定理化简运算

求 7121 mod 137^{121}\bmod 13

解题步骤：

  • 根据费马小定理，712≡1(mod  13)7^{12} ≡ 1 (\mod 13)
  • 那么根据分配律有 (712)k≡1(mod  13)(7^{12})^k ≡ 1 (\mod 13)，k 是任意整数
  • 7121=712⋅10+1=(712)10⋅7≡110⋅7≡7(mod  13)7^{121} = 7^{12 \cdot 10 +1} = (7^{12})^{10} \cdot 7 ≡ 1^{10} \cdot 7 ≡ 7 (\mod 13)

再捋顺下思路，有：7121≡7121 mod 12(mod  13)7^{121} ≡ 7^{121 \bmod 12} (\mod 13)。

即有 xn≡xn mod (p−1)( mod p)x^n ≡ x^{n\bmod (p-1)} (\bmod p)。

相关题目：

矩阵快速幂

相关题目：🟨 P3390 【模板】矩阵快速幂 - 洛谷

本文参考