0372. 超级次方【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 快速幂

1. 📝 题目描述

• leetcode

你的任务是计算 a^b 对 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 <= 2^31 - 1
• 1 <= b.length <= 2000
• 0 <= b[i] <= 9
• b 不含前导 0

2. 🎯 s.1 - 快速幂

c

long long powMod(long long base, int exp, int mod) {
    base %= mod;
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) result = result * base % mod;
        base = base * base % mod;
        exp /= 2;
    }
    return result;
}

int superPow(int a, int* b, int bSize) {
    int mod = 1337;
    long long result = 1;
    for (int i = 0; i < bSize; i++) {
        result = powMod(result, 10, mod) * powMod(a, b[i], mod) % mod;
    }
    return (int)result;
}

js

/**
 * @param {number} a
 * @param {number[]} b
 * @return {number}
 */
var superPow = function (a, b) {
  const MOD = 1337
  const powMod = (base, exp) => {
    base %= MOD
    let result = 1
    while (exp > 0) {
      if (exp % 2 === 1) result = (result * base) % MOD
      base = (base * base) % MOD
      exp = Math.floor(exp / 2)
    }
    return result
  }
  let result = 1
  for (const digit of b) {
    result = (powMod(result, 10) * powMod(a, digit)) % MOD
  }
  return result
}

py

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        MOD = 1337
        result = 1
        for digit in b:
            result = pow(result, 10, MOD) * pow(a, digit, MOD) % MOD
        return result

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $b$ 的长度
• 空间复杂度：$O(1)$

算法思路：

• $a^{1564}=(a^{156}{)}^{10}\times a^4$，逐位处理指数
• 每一位用快速幂取模计算，避免大数溢出