372. 超级次方

Medium

题目描述

你的任务是计算 a^b mod 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

提示：

1 <= a <= 2^31 - 1
1 <= b.length <= 2000
0 <= b[i] <= 9
b 不包含前导零

解题思路

这道题要求计算超大指数的幂运算取模，核心在于处理数组形式的指数。

主要思路：

欧拉定理优化：利用欧拉定理 a^φ(n) ≡ 1 (mod n) 来降低指数的大小
分治递归：将 a^[1,2,3] 拆分为 a^[1,2] * a^3，递归求解
快速幂：对于单个数字的幂运算使用快速幂算法

关键优化：

由于 1337 = 7 × 11 × 17，φ(1337) = 1140
当指数 ≥ 1140 时，可以将指数对 1140 取模再加 1140
这样可以有效减小指数的大小，避免溢出

算法步骤：

实现快速幂函数求 a^k mod 1337
递归处理数组指数：superPow(a, [1,2,3]) = superPow(a, [1,2])^10 * a^3
当指数数组长度超过阈值时，应用欧拉定理优化

这种方法既保证了正确性，又有效控制了计算复杂度。

代码实现

class Solution {
public:
    int superPow(int a, vector<int>& b) {
        const int MOD = 1337;
        const int PHI = 1140; // φ(1337) = 1140
        
        // 快速幂
        function<int(int, int)> quickPow = [&](int base, int exp) -> int {
            int result = 1;
            base %= MOD;
            while (exp > 0) {
                if (exp & 1) result = (1LL * result * base) % MOD;
                base = (1LL * base * base) % MOD;
                exp >>= 1;
            }
            return result;
        };
        
        // 将数组转换为数字 mod PHI
        function<int(vector<int>&)> arrayToNum = [&](vector<int>& arr) -> int {
            int result = 0;
            for (int digit : arr) {
                result = (result * 10 + digit) % PHI;
            }
            return result;
        };
        
        // 检查数组是否 >= PHI
        function<bool(vector<int>&)> isLarge = [&](vector<int>& arr) -> bool {
            if (arr.size() > 4) return true;
            if (arr.size() < 4) return false;
            // 检查是否 >= 1140
            string s = "";
            for (int d : arr) s += to_string(d);
            return stoi(s) >= PHI;
        };
        
        if (isLarge(b)) {
            int exp = arrayToNum(b) + PHI;
            return quickPow(a, exp);
        } else {
            int exp = arrayToNum(b);
            return quickPow(a, exp);
        }
    }
};

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        MOD = 1337
        PHI = 1140  # φ(1337) = 1140
        
        def quick_pow(base, exp):
            result = 1
            base %= MOD
            while exp > 0:
                if exp & 1:
                    result = (result * base) % MOD
                base = (base * base) % MOD
                exp >>= 1
            return result
        
        def array_to_num(arr, mod):
            result = 0
            for digit in arr:
                result = (result * 10 + digit) % mod
            return result
        
        def is_large(arr):
            if len(arr) > 4:
                return True
            if len(arr) < 4:
                return False
            return int(''.join(map(str, arr))) >= PHI
        
        if is_large(b):
            exp = array_to_num(b, PHI) + PHI
            return quick_pow(a, exp)
        else:
            exp = array_to_num(b, float('inf'))
            return quick_pow(a, exp)

public class Solution {
    public int SuperPow(int a, int[] b) {
        const int MOD = 1337;
        const int PHI = 1140; // φ(1337) = 1140
        
        int QuickPow(int baseNum, int exp) {
            int result = 1;
            baseNum %= MOD;
            while (exp > 0) {
                if ((exp & 1) == 1) {
                    result = (int)((long)result * baseNum % MOD);
                }
                baseNum = (int)((long)baseNum * baseNum % MOD);
                exp >>= 1;
            }
            return result;
        }
        
        int ArrayToNum(int[] arr, int mod) {
            int result = 0;
            foreach (int digit in arr) {
                result = (result * 10 + digit) % mod;
            }
            return result;
        }
        
        bool IsLarge(int[] arr) {
            if (arr.Length > 4) return true;
            if (arr.Length < 4) return false;
            string s = string.Join("", arr);
            return int.Parse(s) >= PHI;
        }
        
        if (IsLarge(b)) {
            int exp = ArrayToNum(b, PHI) + PHI;
            return QuickPow(a, exp);
        } else {
            int exp = ArrayToNum(b, int.MaxValue);
            return QuickPow(a, exp);
        }
    }
}

var superPow = function(a, b) {
    const MOD = 1337;
    const PHI = 1140; // φ(1337) = 1140
    
    function quickPow(base, exp) {
        let result = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp & 1) {
                result = (result * base) % MOD;
            }
            base = (base * base) % MOD;
            exp = Math.floor(exp / 2);
        }
        return result;
    }
    
    function arrayToNum(arr, mod) {
        let result = 0;
        for (let digit of arr) {
            result = (result * 10 + digit) % mod;
        }
        return result;
    }
    
    function isLarge(arr) {
        if (arr.length > 4) return true;
        if (arr.length < 4) return false;
        return parseInt(arr.join('')) >= PHI;
    }
    
    if (isLarge(b)) {
        let exp = arrayToNum(b, PHI) + PHI;
        return quickPow(a, exp);
    } else {
        let exp = arrayToNum(b, Number.MAX_SAFE_INTEGER);
        return quickPow(a, exp);
    }
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	大小	说明
时间复杂度	O(n + log a)	n为数组长度，用于处理数组；log a为快速幂的复杂度
空间复杂度	O(1)	只使用常数额外空间

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目