LeetCode周记 EP7

前言

回国了,开始好好准备找工。

本周主题:快速幂

题目:

快速幂

「快速幂算法」的本质是分治算法。举个例子,如果我们要计算 $x^{64}$ ,我们可以按照:

的顺序,从 $x$ 开始,每次直接把上一次的结果进行平方,计算 6 次就可以得到 $x^{64}$ 的值,而不需要对 $x$ 乘 63 次 $x$ 。

再举一个例子,如果我们要计算 $x^{77}$ ,我们可以按照:

的顺序, 在 $x \rightarrow x^2, x^2 \rightarrow x^4, x^{19} \rightarrow x^{38}$ 这些步骤中, 我们直接把上一次的结果进行平方,而在 $x^4 \rightarrow x^9, x^9 \rightarrow x^{19}, x^{38} \rightarrow x^{77}$ 这些步骤中,我们把上一次的结果进行平方后,还要额外乘一个 $x$ 。

直接从左到右进行推导看上去很困难,因为在每一步中,我们不知道在将上一次的结果平方之后, 还需不需要额外乘 $x$ 。但如果我们从右往左看, 分治的思想就十分明显了:

  • 当我们要计算 $x^n$ 时,我们可以先递归地计算出 $y=x^{\lfloor n / 2\rfloor}$ ,其中 $\lfloor a\rfloor$表示对 $a$ 进行下取整;
  • 根据递归计算的结果, 如果 $n$ 为偶数, 那么 $x^n=y^2$; 如果 $n$ 为奇数,那么 $x^n=y^2 \times x$ ;
  • 递归的边界为 $n=0$, 任意数的 0 次方均为 1 。

由于每次递归都会使得指数减少一半,因此递归的层数为 O(logn),算法可以在很快的时间内得到结果。

下面是快速幂算法的递归实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public double myPow(double x, int n) {
long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}

public double quickMul(double x, long N) {
if (N == 0) {
return 1.0;
}
double y = quickMul(x, N / 2);
return N % 2 == 0 ? y * y : y * y * x;
}
}

进一步,由于递归需要使用额外的栈空间,我们试着将递归转写为迭代。我们还是以 $x^{77}$ 作为例子:

并且把需要额外乘 $x$ 的步骤打上了 + 标记。可以发现:

  • $x^{38} \rightarrow^{+} x^{77}$ 中额外乘的 $x$ 在 $x^{77}$ 中贡献了 $x$ ;
  • $x^9 \rightarrow^{+} x^{19}$ 中额外乘的 $x$ 在之后被平方了 2 次,因此在 $x^{77}$ 中贡献了 $x^{2^2}=x^4$
  • $x^4 \rightarrow^{+} x^9$ 中额外乘的 $x$ 在之后被平方了 3 次,因此在 $x^{77}$ 中贡献了 $x^{2^3}=x^8$
  • 最初的 $x$ 在之后被平方了 6 次,因此在 $x^{77}$ 中贡献了 $x^{2^6}=x^{64}$ 。

我们把这些贡献相乘, $x \times x^4 \times x^8 \times x^{64}$ 恰好等于 $x^{77}$ 。而这些贡献的指数部分又是什么呢?它们都是 2 的幂次,这是因为每个额外乘的 $x$ 在之后都会被平方若干次。而这些指数 $1 , 4 , 8$ 和 $64 ,$ 恰好就对应了 77 的二进制表示 $(1001101)_2$ 中的每个 1 !

因此我们借助整数的二进制拆分,就可以得到迭代计算的方法,一般地,如果整数 $n$ 的二进制拆分为

那么

这样以来, 我们从 $x$ 开始不断地进行平方, 得到 $x^2, x^4, x^8, x^{16}, \cdots$, 如果 $n$的第 $k$ 个(从右往左,从 0 开始计数)二进制位为 1 ,那么我们就将对应的贡献 $x^{2^k}$ 计入答案。

下面是快速幂的迭代实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public double myPow(double x, int n) {
long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}

public double quickMul(double x, long N) {
double ans = 1.0;
// 贡献的初始值为 x0
double 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;
}
}

例题:Double Modular Exponentiation

Double Modular Exponentiation

You are given a 0-indexed 2D array variables where variables[i] = [ai, bi, ci, mi], and an integer target.

An index i is good if the following formula holds:

  • 0 <= i < variables.length
  • ((ai^bi % 10)^ci) % mi == target

Return an array consisting of good indices in any order.

计算式中重复出现的模式是“幂+取模”,于是可以把快速幂和取模融合在一起。

另一个知识点是“加法和乘法”的取模,有如下公式:
$(a+b) \bmod m=((a \bmod m)+(b \bmod m)) \bmod m$ $(a \cdot b) \bmod m=((a \bmod m) \cdot(b \bmod m)) \bmod m$

因此我们可以在计算过程中(例如循环),对加法和乘法的结果取模,而不是在循环结束后再取模。

更多模相关的内容请看:https://leetcode.cn/circle/discuss/mDfnkW/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public List<Integer> getGoodIndices(int[][] variables, int target) {
List<Integer> ans = new ArrayList<Integer>();
for (int i = 0; i < variables.length; i++) {
int[] v = variables[i];
if (powMod(powMod(v[0], v[1], 10), v[2], v[3]) == target) {
ans.add(i);
}
}
return ans;
}

public int powMod(int x, int y, int mod) {
int res = 1;
// (a*b) mod c = ((a mod c) * (b mod c)) mod c
while (y != 0) {
if ((y & 1) != 0) {
res = res * x % mod;
}
x = x * x % mod;
y >>= 1; // 相当于y/=2
}
return res;
}
}

参考文献

[1] https://leetcode.cn/circle/discuss/mDfnkW/
[2] https://leetcode.cn/problems/powx-n/solutions/238559/powx-n-by-leetcode-solution/

后记

首发于 silencezheng.top,转载请注明出处。


LeetCode周记 EP7
http://silencezheng.top/2024/08/07/article131/
作者
SilenceZheng66
发布于
2024年8月7日
许可协议