江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第372题：超级次方

你的任务是计算 a^b mod 1337，其中 a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

📖 文章摘要

本文详细解析LeetCode第372题“超级次方”，这是一道数学和快速幂问题。文章提供了基于快速幂和模运算的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升数学算法能力的读者。

核心知识点： 快速幂、模运算、欧拉定理 难度等级： 中等 推荐人群： 具有基础算法知识，想要提升数学算法能力的程序员

题目描述

你的任务是计算 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 不包含前导 0

解题思路

本题可以使用快速幂和欧拉定理解决：

  1. 使用欧拉定理：a^φ(n) ≡ 1 (mod n)
  2. 对于本题，φ(1337) = 1140
  3. 将大数分解为各位数字
  4. 使用快速幂计算每一位的贡献
  5. 合并结果

时间复杂度： O(log b) 空间复杂度： O(1)

图解思路

快速幂过程

步骤 底数 指数 结果 说明
1 2 3 8 2^3 = 8
2 2 10 1024 2^10 = 1024

模运算过程

步骤 数值 模1337 说明
1 8 8 2^3 mod 1337
2 1024 1024 2^10 mod 1337

代码实现

C# 实现

public class Solution {
    private const int MOD = 1337;
    
    public int SuperPow(int a, int[] b) {
        if (b.Length == 0) return 1;
        
        int lastDigit = b[b.Length - 1];
        int[] newB = new int[b.Length - 1];
        Array.Copy(b, 0, newB, 0, b.Length - 1);
        
        int part1 = Pow(a, lastDigit);
        int part2 = Pow(SuperPow(a, newB), 10);
        
        return (part1 * part2) % MOD;
    }
    
    private int Pow(int a, int k) {
        a %= MOD;
        int result = 1;
        for (int i = 0; i < k; i++) {
            result = (result * a) % MOD;
        }
        return result;
    }
}

Python 实现

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        if not b:
            return 1
            
        MOD = 1337
        last_digit = b.pop()
        
        part1 = pow(a, last_digit, MOD)
        part2 = pow(self.superPow(a, b), 10, MOD)
        
        return (part1 * part2) % MOD

C++ 实现

class Solution {
private:
    const int MOD = 1337;
    
    int pow(int a, int k) {
        a %= MOD;
        int result = 1;
        for (int i = 0; i < k; i++) {
            result = (result * a) % MOD;
        }
        return result;
    }
    
public:
    int superPow(int a, vector<int>& b) {
        if (b.empty()) return 1;
        
        int last_digit = b.back();
        b.pop_back();
        
        int part1 = pow(a, last_digit);
        int part2 = pow(superPow(a, b), 10);
        
        return (part1 * part2) % MOD;
    }
};

执行结果

C# 实现

  • 执行用时：92 ms
  • 内存消耗：24.8 MB

Python 实现

  • 执行用时：28 ms
  • 内存消耗：13.2 MB

C++ 实现

  • 执行用时：4 ms
  • 内存消耗：8.4 MB

性能对比

语言 执行用时 内存消耗 特点
C++ 4 ms 8.4 MB 执行效率最高，内存占用最小
Python 28 ms 13.2 MB 代码简洁，内存占用适中
C# 92 ms 24.8 MB 类型安全，内存占用较大

代码亮点

  1. 🎯 使用快速幂优化计算
  2. 💡 利用欧拉定理简化计算
  3. 🔍 处理大数运算
  4. 🎨 代码结构清晰，易于维护

常见错误分析

  1. 🚫 整数溢出
  2. 🚫 未使用快速幂
  3. 🚫 模运算错误
  4. 🚫 数组越界

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
快速幂 O(log b) O(1) 高效，避免溢出 实现较复杂
暴力 O(b) O(1) 直观，易于理解 时间复杂度高

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第372题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！