文章目录
- 摘要
- 描述
- 题解答案
- 题解代码分析
- 代码解析
- 示例测试及结果
- 时间复杂度
- 空间复杂度
- 总结
摘要
在算法题里，有一些问题看似“简单”，比如算一个幂次方，但一旦放大规模就完全不同了。LeetCode 372 超级次方就是这样的题目。普通的幂运算没什么难度，但当指数 b 是一个用数组表示的上千位数字时，直接计算会导致溢出或者运行缓慢。本文会结合 Swift 给出可运行的解题方案，并分析其原理和实际应用场景。
描述
题目的要求是：
计算 a^b % 1337，其中：
a是一个正整数（范围在 1 到 2³¹-1 之间）b是一个非常大的正整数，并且用数组形式存储（数组每一位是b的十进制数字）。
举几个例子：
a = 2, b = [3]→2^3 % 1337 = 8a = 2, b = [1,0]→2^10 % 1337 = 1024a = 1, b = [4,3,3,8,5,2]→ 无论怎么幂次，结果都是1a = 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 Foundationclass Solution {private let MOD = 1337func 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 = blet 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 = 1var b = base % MODvar p = powerwhile p > 0 {if p % 2 == 1 {result = (result * b) % MOD}b = (b * b) % MODp /= 2}return result}
}
代码解析
-
superPow：入口函数，先对a取模，避免不必要的大数计算。 -
helper：递归函数，把数组b的最后一位拿出来处理。part1 = a^lastDigit % MODpart2 = (a^rest)^10 % MOD- 然后组合结果
(part1 * part2) % MOD
-
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))。
总结
这道题的精髓在于：
- 不能直接算，要学会把指数拆分。
- 快速幂 + 模运算是大数幂问题的通用解法。
- 实际场景里，类似的思路常见于加密算法（比如 RSA），因为加密里经常需要计算“大数的模幂运算”。
所以这题不仅仅是算法训练题，还能让我们更好地理解实际中的密码学和大数运算的实现方式。
)
