文章目錄
- 摘要
- 描述
- 題解答案
- 題解代碼分析
- 代碼解析
- 示例測試及結果
- 時間復雜度
- 空間復雜度
- 總結
摘要
在算法題里，有一些問題看似“簡單”，比如算一個冪次方，但一旦放大規模就完全不同了。LeetCode 372 超級次方就是這樣的題目。普通的冪運算沒什么難度，但當指數 b 是一個用數組表示的上千位數字時，直接計算會導致溢出或者運行緩慢。本文會結合 Swift 給出可運行的解題方案，并分析其原理和實際應用場景。
描述
題目的要求是：
計算 a^b % 1337，其中：
a是一個正整數（范圍在 1 到 231-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），因為加密里經常需要計算“大數的模冪運算”。
所以這題不僅僅是算法訓練題，還能讓我們更好地理解實際中的密碼學和大數運算的實現方式。
)
