0372-超级次方

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 15:32:51 2023-09-13 15:32:51 Updated    

你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

示例 1：

**输入：** a = 2, b = [3]
**输出：** 8

示例 2：

**输入：** a = 2, b = [1,0]
**输出：** 1024

示例 3：

**输入：** a = 1, b = [4,3,3,8,5,2]
**输出：** 1

示例 4：

**输入：** a = 2147483647, b = [2,0,0]
**输出：** 1198

提示：

  • 1 <= a <= 231 - 1
  • 1 <= b.length <= 2000
  • 0 <= b[i] <= 9
  • b 不含前导 0

前置知识

在阅读本文前，读者需要掌握快速幂这一算法，具体可以见「50. Pow(x, n) 的官方题解 」。

此外，乘法在取模的意义下满足分配律，即

$$
(a \cdot b) \bmod m = [(a \bmod m) \cdot (b \bmod m)] \bmod m
$$

方法一：倒序遍历

设 $a$ 的幂次为 $n$。根据题意，$n$ 从最高位到最低位的所有数位构成了数组 $b$。记数组 $b$ 的长度为 $m$，有

$$
n=\sum\limits_{i=0}^{m-1} 10^{m-1-i} \cdot b_i
$$

由于 $a^{x+y}=a^x\cdot a^y$ 以及 $a^{x\cdot y} = (a^x)^y$，得

$$
a^n = \prod\limits_{i=0}^{m-1} a^{10^{m-1-i} \cdot b_i} = \prod\limits_{i=0}^{m-1} \Big(a^{10^{m-1-i}}\Big)^{b_i}
$$

可以根据如下等式计算上式括号内的部分：

$$
a^{10^k} = a^{10^{k-1}\cdot 10} = \Big(a^{10^{k-1}}\Big)^{10}
$$

我们可以从 $a^1$ 开始，递推地计算出 $a^{10^k。

代码实现时，可以从 $b_{m-1 开始倒序计算，在计算的过程中同时递推计算出 $a^{10^k。

[sol1-Python3]
1
2
3
4
5
6
7
8
class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        MOD = 1337
        ans = 1
        for e in reversed(b):
            ans = ans * pow(a, e, MOD) % MOD
            a = pow(a, 10, MOD)
        return ans
[sol1-C++]
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 {
    const int MOD = 1337;

    int pow(int x, int n) {
        int res = 1;
        while (n) {
            if (n % 2) {
                res = (long) res * x % MOD;
            }
            x = (long) x * x % MOD;
            n /= 2;
        }
        return res;
    }

public:
    int superPow(int a, vector<int> &b) {
        int ans = 1;
        for (int i = b.size() - 1; i >= 0; --i) {
            ans = (long) ans * pow(a, b[i]) % MOD;
            a = pow(a, 10);
        }
        return ans;
    }
};
[sol1-Java]
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 {
    static final int MOD = 1337;

    public int superPow(int a, int[] b) {
        int ans = 1;
        for (int i = b.length - 1; i >= 0; --i) {
            ans = (int) ((long) ans * pow(a, b[i]) % MOD);
            a = pow(a, 10);
        }
        return ans;
    }

    public int pow(int x, int n) {
        int res = 1;
        while (n != 0) {
            if (n % 2 != 0) {
                res = (int) ((long) res * x % MOD);
            }
            x = (int) ((long) x * x % MOD);
            n /= 2;
        }
        return res;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    const int MOD = 1337;

    public int SuperPow(int a, int[] b) {
        int ans = 1;
        for (int i = b.Length - 1; i >= 0; --i) {
            ans = (int) ((long) ans * Pow(a, b[i]) % MOD);
            a = Pow(a, 10);
        }
        return ans;
    }

    public int Pow(int x, int n) {
        int res = 1;
        while (n != 0) {
            if (n % 2 != 0) {
                res = (int) ((long) res * x % MOD);
            }
            x = (int) ((long) x * x % MOD);
            n /= 2;
        }
        return res;
    }
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const mod = 1337

func pow(x, n int) int {
    res := 1
    for ; n > 0; n /= 2 {
        if n&1 > 0 {
            res = res * x % mod
        }
        x = x * x % mod
    }
    return res
}

func superPow(a int, b []int) int {
    ans := 1
    for i := len(b)-1; i >= 0; i-- {
        ans = ans * pow(a, b[i]) % mod
        a = pow(a, 10)
    }
    return ans
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const MOD = BigInt(1337);

var superPow = function(a, b) {
    let ans = BigInt(1);
    for (let i = b.length - 1; i >= 0; --i) {
        ans = ans * pow(BigInt(a), b[i]) % MOD;
        a = pow(BigInt(a), 10);
    }
    return ans;
};

const pow = (x, n) => {
    let res = BigInt(1);
    while (n !== 0) {
        if (n % 2 !== 0) {
            res = res * BigInt(x) % MOD;
        }
        x = x * x % MOD;
        n = Math.floor(n / 2);
    }
    return res;
}

复杂度分析

  • 时间复杂度：$O(\sum\limits_{i=0}^{m-1} \log b_i)$，其中 $m$ 是数组 $b$ 的长度。对每个 $b_i$ 计算快速幂的时间为 $O(\log b_i)$。

  • 空间复杂度：$O(1)$，只需要常数的空间存放若干变量。

方法二：秦九韶算法（正序遍历）

由于

$$
n = \sum\limits_{i=0}^{m-1} 10^{m-1-i} \cdot b_i = \Big(\sum\limits_{i=0}^{m-2} 10^{m-2-i} \cdot b_i\Big)\cdot 10 + b_{m-1}
$$

记 $n’=\sum\limits_{i=0}^{m-2} 10^{m-2-i} \cdot b_i$，有

$$
a^n = a^{n’\cdot 10 + b_{m-1}} = (a^{n’})^{10}\cdot a^{b_{m-1}}
$$

根据该式，可以得到如下递推式：

$$
\textit{superPow}(a,b) =
\begin{cases}
1,&m=0\
\textit{superPow}(a,b’)^{10}\cdot a^{b_{m-1}},&m\ge 1
\end{cases}
$$

其中 $b’$ 为 $b$ 去掉末尾元素后的部分。

[sol2-Python3]
1
2
3
4
5
6
7
class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        MOD = 1337
        ans = 1
        for e in b:
            ans = pow(ans, 10, MOD) * pow(a, e, MOD) % MOD
        return ans
[sol2-C++]
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 {
    const int MOD = 1337;

    int pow(int x, int n) {
        int res = 1;
        while (n) {
            if (n % 2) {
                res = (long) res * x % MOD;
            }
            x = (long) x * x % MOD;
            n /= 2;
        }
        return res;
    }

public:
    int superPow(int a, vector<int> &b) {
        int ans = 1;
        for (int e: b) {
            ans = (long) pow(ans, 10) * pow(a, e) % MOD;
        }
        return ans;
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    static final int MOD = 1337;

    public int superPow(int a, int[] b) {
        int ans = 1;
        for (int e : b) {
            ans = (int) ((long) pow(ans, 10) * pow(a, e) % MOD);
        }
        return ans;
    }

    public int pow(int x, int n) {
        int res = 1;
        while (n != 0) {
            if (n % 2 != 0) {
                res = (int) ((long) res * x % MOD);
            }
            x = (int) ((long) x * x % MOD);
            n /= 2;
        }
        return res;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    const int MOD = 1337;

    public int SuperPow(int a, int[] b) {
        int ans = 1;
        foreach (int e in b) {
            ans = (int) ((long) Pow(ans, 10) * Pow(a, e) % MOD);
        }
        return ans;
    }

    public int Pow(int x, int n) {
        int res = 1;
        while (n != 0) {
            if (n % 2 != 0) {
                res = (int) ((long) res * x % MOD);
            }
            x = (int) ((long) x * x % MOD);
            n /= 2;
        }
        return res;
    }
}
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const mod = 1337

func pow(x, n int) int {
    res := 1
    for ; n > 0; n /= 2 {
        if n&1 > 0 {
            res = res * x % mod
        }
        x = x * x % mod
    }
    return res
}

func superPow(a int, b []int) int {
    ans := 1
    for _, e := range b {
        ans = pow(ans, 10) * pow(a, e) % mod
    }
    return ans
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const MOD = BigInt(1337);

var superPow = function(a, b) {
    let ans = 1;
    for (const e of b) {
        ans = pow(BigInt(ans), 10) * pow(BigInt(a), e) % MOD;
    }
    return ans;
};

const pow = (x, n) => {
    let res = BigInt(1);
    while (n !== 0) {
        if (n % 2 !== 0) {
            res = res * BigInt(x) % MOD;
        }
        x = x * x % MOD;
        n = Math.floor(n / 2);
    }
    return res;
}

复杂度分析

  • 时间复杂度：$O(\sum\limits_{i=0}^{m-1} \log b_i)$，其中 $m$ 是数组 $b$ 的长度。对每个 $b_i$ 计算快速幂的时间为 $O(\log b_i)$。

  • 空间复杂度：$O(1)$，只需要常数的空间存放若干变量。

 Comments
On this page
0372-超级次方