372. 超级次方

🟠   🔖  数学 分治  🔗 力扣 LeetCode

题目

Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example 1:

Input: a = 2, b = [3]

Output: 8

Example 2:

Input: a = 2, b = [1,0]

Output: 1024

Example 3:

Input: a = 1, b = [4,3,3,8,5,2]

Output: 1

Constraints:

• 1 <= a <= 2^31 - 1
• 1 <= b.length <= 2000
• 0 <= b[i] <= 9
• b does not contain leading zeros.

题目大意

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

解题思路

1. 利用 指数运算的分解性质：

• (x^m * x^n) % mod = ((x^m) % mod * (x^n) % mod) % mod
• 设 b = [d1, d2, ..., dn]，可表示为 b = d1 * 10^(n-1) + d2 * 10^(n-2) + ... + dn。

可以通过递归计算：

a^b = a^(d1 * 10^(n-1)) * a^(d2 * 10^(n-2)) * ... * a^dn

2. 使用快速幂来计算 (x^y) % mod：

• 将 y 按位分解。
  • 若 y 为奇数，则结果乘以 x；
  • 否则只计算平方部分。

复杂度分析

• 时间复杂度：O(n log 10)，n 是数组 b 的长度，每次递归需要计算一个快速幂。
• 空间复杂度：O(n)，递归栈空间。

代码

/**
 * @param {number} a
 * @param {number[]} b
 * @return {number}
 */
var superPow = function (a, b) {
	if (b.length == 0) return 1;
	const mod = 1337;
	const num = b.pop();
	// 递归
	return (modPow(superPow(a, b), 10) * modPow(a, num)) % mod;
};

// 快速幂计算 (x^y) % mod
var modPow = function (x, y) {
	const mod = 1337;
	let res = 1;
	x %= mod;
	while (y > 0) {
		if (y % 2 == 1) {
			res = (res * x) % mod;
		}
		x = (x * x) % mod;
		y = Math.floor(y / 2);
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
50	Pow(x, n)	[✓]	递归 数学	🟠	🀄️ 🔗