LeetCode周记 EP7

2024-08-07

字数统计: 1.5k字 | 阅读时长: 6分

前言

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

本周主题：快速幂

题目：

240730每日一题—Double Modular Exponentiation

快速幂

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

$x \rightarrow x^2 \rightarrow x^4 \rightarrow x^8 \rightarrow x^{16} \rightarrow x^{32} \rightarrow x^{64}$

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

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

$x \rightarrow x^2 \rightarrow x^4 \rightarrow x^9 \rightarrow x^{19} \rightarrow x^{38} \rightarrow 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)，算法可以在很快的时间内得到结果。

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

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 \rightarrow x^2 \rightarrow x^4 \rightarrow^{+} x^9 \rightarrow^{+} x^{19} \rightarrow x^{38} \rightarrow^{+} 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$ 的二进制拆分为

$n=2^{i_0}+2^{i_1}+\cdots+2^{i_k}$

那么

$x^n=x^{2^{i_0}} \times x^{2^{i_1}} \times \cdots \times x^{2^{i_k}}$

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

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

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/

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，转载请注明出处。