Swift 解题：LeetCode 372 超级次方（Super Pow）

摘要

在算法题里，有一些问题看似“简单”，比如算一个幂次方，但一旦放大规模就完全不同了。LeetCode 372 超级次方就是这样的题目。普通的幂运算没什么难度，但当指数 b 是一个用数组表示的上千位数字时，直接计算会导致溢出或者运行缓慢。本文会结合 Swift 给出可运行的解题方案，并分析其原理和实际应用场景。

描述

题目的要求是：
计算 a^b % 1337，其中：

• a 是一个正整数（范围在 1 到 2³¹-1 之间）
• b 是一个非常大的正整数，并且用数组形式存储（数组每一位是 b 的十进制数字）。

举几个例子：

1. a = 2, b = [3] → 2^3 % 1337 = 8
2. a = 2, b = [1,0] → 2^10 % 1337 = 1024
3. a = 1, b = [4,3,3,8,5,2] → 无论怎么幂次，结果都是 1
4. a = 2147483647, b = [2,0,0] → 结果 1198

核心难点：

• b 太大了，不能直接转成整数再做幂运算。

• 普通幂运算会溢出，需要用模幂运算（modular exponentiation）。

• 幂运算的拆分技巧：

  • a^(b1b2...bn) = ((a^(b1b2...bn-1))^10 * a^bn) % mod

题解答案

这题的关键在于“分治 + 快速幂 + 模运算”。
我们要不断从 b 的最后一位往前处理，把指数拆分为小块，然后应用公式：

a^1234 = ((a^123)^10) * a^4

这样我们就能一位一位处理 b，避免溢出。

题解代码分析

下面是 Swift 的解法：

import Foundation

class Solution {
    private let MOD = 1337
    
    func superPow(_ a: Int, _ b: [Int]) -> Int {
        return helper(a % MOD, b)
    }
    
    private func helper(_ a: Int, _ b: [Int]) -> Int {
        if b.isEmpty { return 1 }
        
        // 取出最后一位
        var newB = b
        let lastDigit = newB.removeLast()
        
        // 计算 (a^lastDigit % MOD)
        let part1 = modPow(a, lastDigit)
        
        // 计算 ((a^rest)^10 % MOD)
        let part2 = modPow(helper(a, newB), 10)
        
        return (part1 * part2) % MOD
    }
    
    // 快速幂取模
    private func modPow(_ base: Int, _ power: Int) -> Int {
        var result = 1
        var b = base % MOD
        var p = power
        
        while p > 0 {
            if p % 2 == 1 {
                result = (result * b) % MOD
            }
            b = (b * b) % MOD
            p /= 2
        }
        return result
    }
}

代码解析

1. superPow：入口函数，先对 a 取模，避免不必要的大数计算。

2. helper：递归函数，把数组 b 的最后一位拿出来处理。

   • part1 = a^lastDigit % MOD
   • part2 = (a^rest)^10 % MOD
   • 然后组合结果 (part1 * part2) % MOD

3. modPow：快速幂函数，通过二分法计算 (base^power) % MOD，避免指数过大。

这种写法巧妙地利用了指数展开公式和快速幂，既避免了大数溢出，也保证了运行效率。

示例测试及结果

我们用几个例子跑一下：

let solution = Solution()

print(solution.superPow(2, [3]))              // 输出: 8
print(solution.superPow(2, [1,0]))           // 输出: 1024
print(solution.superPow(1, [4,3,3,8,5,2]))   // 输出: 1
print(solution.superPow(2147483647, [2,0,0])) // 输出: 1198

运行结果：

8
1024
1
1198

跟题目给的示例完全一致

时间复杂度

• 快速幂函数 modPow 的时间复杂度是 O(log power)。
• 我们对 b 的每一位数字都要调用一次 modPow，所以总复杂度是 O(len(b) * log a)。
• 对于 len(b) <= 2000，这个复杂度是完全可以接受的。

空间复杂度

• 递归的深度取决于 b 的长度，最多 2000。
• 所以空间复杂度是 O(len(b))。

总结

这道题的精髓在于：

1. 不能直接算，要学会把指数拆分。
2. 快速幂 + 模运算是大数幂问题的通用解法。
3. 实际场景里，类似的思路常见于加密算法（比如 RSA），因为加密里经常需要计算“大数的模幂运算”。

所以这题不仅仅是算法训练题，还能让我们更好地理解实际中的密码学和大数运算的实现方式。