Fast Exponentiation快速冪

01為什麼需要它

看到這些關鍵字就想到它：x 的 n 次方、n 很大（10⁹、10¹⁸）、答案取模、RSA 與模冪、線性遞推第 n 項、矩陣的 n 次方、重複套用同一個操作 n 次、乘法次數要 O(log n)。

02核心概念

算 xⁿ 最直接是乘 n − 1 次。快速冪用分治把指數切半：xⁿ = (x^⌊n/2⌋)²，n 是奇數時再多乘一個 x。算出一半、平方一次就得到全部，遞迴式是 T(n) = T(n/2) + O(1)，套 Master Theorem 的 a = 1、b = 2、d = 0 落在情況 2，是 O(log n) 次乘法。最常見的錯是把 power(x, n/2) 呼叫兩次再相乘：遞迴式變成 T(n) = 2T(n/2) + O(1)，又回到 O(n)，關鍵在「一半只算一次」。

迭代版從二進位看同一件事。把 n 寫成 Σ bᵢ·2ⁱ，就有 xⁿ = ∏ x^(2ⁱ)，只乘 bᵢ = 1 的那幾項。從最低位往最高位掃，維持兩個不變量：處理第 i 位之前，base = x^(2ⁱ)，result = x^(n 的低 i 位)。第 i 位是 1 就把 base 乘進 result，然後 base 平方變成 x^(2ⁱ⁺¹)、n 右移一位。所有位元處理完，低位就是整個 n，result 正是 xⁿ。這個寫法不用遞迴，額外空間 O(1)。

複雜度：n 有 ⌊log₂ n⌋ + 1 個位元，每一位最多一次平方加一次乘法，總共不超過 2 log₂ n 次乘法；指數變成十倍，位元只多 3、4 個。這裡的 O(log n) 是「乘法的次數」：取模運算的每次乘法是 O(1)；沒有取模的大整數，數字越乘越長，每次乘法本身就越來越貴。空間上迭代版 O(1)，遞迴版要 O(log n) 的呼叫堆疊。快速冪只用到結合律和一個「1」（單位元素），所以不只適用於數字：矩陣的「1」是單位矩陣，一次 k×k 矩陣乘法 O(k³)，整體 O(k³ log n)，這就是用矩陣快速冪算線性遞推第 n 項的做法；置換、仿射變換等可以合成的操作也都能這樣「倍增」。

常見的坑：溢位，每做一次乘法就要取模，而且兩個小於 mod 的數相乘必須放得進型別，mod = 10⁹+7 時 64 位元整數夠用，mod 接近 10¹⁸ 時就要 128 位元或特別的乘法；負指數（LeetCode 50）要先取倒數，而 32 位元的 INT_MIN 直接取負會溢位，先轉成 64 位元；x⁰ = 1 包括 x = 0 的情況，而 mod = 1 時答案應該是 0，所以初值寫 1 % mod。和相鄰課程的關係：Master Theorem 那篇的二分搜尋和這裡是同一個遞迴式；數學主題的 Modular Arithmetic 會用快速冪算模反元素，也就是費馬小定理的 a^(p−2) mod p。

03演算法步驟

1. 1初始化 result = 1 % mod、base = x % mod。
2. 2當 n > 0：若 n & 1 是 1，result = result × base % mod。
3. 3base = base × base % mod，n >>= 1，回到上一步。每一輪處理 n 的一個位元。
4. 4n 變成 0 時 result 就是答案。遞迴寫法則是先算 half = power(x, n // 2)，回傳 half² 或 half² × x，一半只算一次。
5. 5換成矩陣或其他可結合的操作時，把 1 換成單位元素、把乘法換成那個操作，其餘完全不變。

04互動示範

底數固定是 3，可以切換指數 13、25、100。上方是指數的二進位，右邊是最低位，上排標出每一位的權重；從最低位往最高位一格一格處理，藍色是正在處理的位元，處理過的位元是 1 就變綠色。表格記下每一位時的 base（也就是 3 的 2ⁱ 次方）以及 result，所有乘法都對 10⁹+7 取模。右側兩條長條比較乘法次數：指數 13 要 6 次、25 要 7 次、100 只要 9 次，逐次相乘分別是 12、24、99 次。

05程式碼

Python 放遞迴版、迭代的模冪，以及把同一套迴圈套在 2×2 矩陣上算費氏數列第 10¹⁸ 項。C++ 放模冪、處理浮點數與負指數的 LeetCode 50 寫法（注意 INT_MIN），和矩陣快速冪。三個迴圈長得一模一樣，差別只在「1」和「乘法」是什麼。

# 遞迴版：x^n = (x^(n//2))²，n 是奇數再多乘一個 x
def power_rec(x, n):
    if n == 0:
        return 1
    half = power_rec(x, n // 2)          # 只遞迴一次；寫成兩次呼叫就退化成 O(n)
    return half * half * (x if n % 2 else 1)


# 迭代版：由低位往高位掃 n 的二進位，base 每一輪平方
def power_mod(x, n, mod):
    result, base = 1 % mod, x % mod
    while n > 0:
        if n & 1:                        # 這一位是 1：把 x^(2^i) 乘進答案
            result = result * base % mod
        base = base * base % mod         # x^(2^i) → x^(2^(i+1))
        n >>= 1
    return result


# 同一套做法換成矩陣：[[1, 1], [1, 0]]^n = [[F(n+1), F(n)], [F(n), F(n-1)]]
def mat_mul(A, B, mod):
    return [[(A[0][0] * B[0][0] + A[0][1] * B[1][0]) % mod, (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % mod],
            [(A[1][0] * B[0][0] + A[1][1] * B[1][0]) % mod, (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % mod]]


def fib_mod(n, mod):
    result, base = [[1, 0], [0, 1]], [[1, 1], [1, 0]]   # 單位矩陣就是矩陣的「1」
    while n > 0:
        if n & 1:
            result = mat_mul(result, base, mod)
        base = mat_mul(base, base, mod)
        n >>= 1
    return result[0][1]                  # 右上角是 F(n)


if __name__ == "__main__":
    print(power_rec(3, 13), power_rec(2, 10))      # 1594323 1024
    MOD = 10**9 + 7
    print(power_mod(3, 25, MOD), pow(3, 25, MOD))  # 288603514 288603514（內建三參數 pow 就是快速冪）
    print(fib_mod(10, MOD), fib_mod(10**18, MOD))  # 55 209783453（第 10¹⁸ 項只要約 60 輪）

06練習題

• LeetCode 509Fibonacci Number（用矩陣快速冪做到 O(log n)）Easy
• LeetCode 50Pow(x, n)（負指數與 INT_MIN）Medium
• LeetCode 1922Count Good Numbers（n 到 10¹⁵，答案是兩個模冪相乘）Medium
• LeetCode 372Super Pow（指數是一個超長的十進位陣列）Medium
• LeetCode 1969Minimum Non-Zero Product of the Array Elements（先推出公式，再用模冪算）Medium