算 aⁿ 不用乘 n 次。靠「平方 + 看二進位」只要 O(log n),連費氏數都能秒算。
aⁿ 最笨的方法是乘 n−1 次(O(n))。快速冪用一個平方技巧:aⁿ = (a^(n/2))²,一路對半拆,只要 O(log n) 次乘法。換個角度看:把 n 拆成二進位,把 a 不斷平方(a, a², a⁴, a⁸…),遇到二進位是 1 的位就把當下的平方乘進答案。這招不只用在數字 —— 把「乘法」換成矩陣乘法,就是矩陣快速冪,能在 O(log n) 算出費氏數、任何線性遞迴。密碼學(RSA 的模冪)、字串雜湊、遞迴加速都靠它。
平方拆一半 —— aⁿ = (a^(n/2))²(n 偶),aⁿ = a · a^(n−1)(n 奇)。每拆一次指數少一半,所以只要 O(log n) 步。
二進位視角 —— 把 a 不斷平方得到 a^1, a^2, a^4, a^8…(每個是前一個的平方)。n 寫成二進位,哪一位是 1,就把對應的 a^(2^位) 乘進答案。
例:3¹³ —— 13 = 1101₂,所以 3¹³ = 3^8 · 3^4 · 3^1(第 3、2、0 位是 1)。只做了幾次乘法,不是 12 次。
迭代版超短 —— while n: if n&1: r*=a; a*=a; n>>=1。每輪把 base 平方、n 右移一位,是 1 就乘進 r。
算 (aⁿ) mod m —— RSA 加解密、Diffie-Hellman、雜湊都要對超大的指數取模。
每步都取模 —— 把每次乘法後都 % m,數字就永遠不會爆掉:r = r*a % m、a = a*a % m。
Python 內建 pow(a, n, m) —— 其實就是高效模冪,直接用即可。但懂原理才知道它為什麼快、為什麼安全。
一模一樣的演算法,乘法換成矩陣乘法 —— 快速冪的骨架完全不變,只是 base、result 從數字變成矩陣,1 變成單位矩陣。
費氏數:M = [[1,1],[1,0]] —— 神奇的是 Mⁿ = [[F(n+1), F(n)], [F(n), F(n−1)]]。所以算 Mⁿ 就等於算 F(n),只要 O(log n)!
任何線性遞迴都能這樣加速 —— a(n) = c₁·a(n−1) + c₂·a(n−2) + … 都能寫成「狀態向量 × 轉移矩陣」,再用矩陣快速冪跳到第 n 項。
複雜度 O(k³ log n) —— k 是矩陣邊長(遞迴階數)。就算 n = 10¹⁸,取模後也能瞬間算出來。
log n。O(k³),共 log n 次。O(k²))。算 2¹⁰⁰ 不用乘 100 次:先算 2⁵⁰,平方一下就好;2⁵⁰ 又從 2²⁵ 來…一路對半。
把 n 拆成二進位,只有是 1 的位才把對應的平方乘進答案,其他位跳過。
矩陣快速冪讓 F(10¹⁸)(取模)一瞬間算出來,不用一項一項加。
兩個情境用完全一樣的快速冪骨架,差別只在乘法。13 = 1101₂,一路把 base 平方(base¹→²→⁴→⁸),遇到是 1 的位就把 base 乘進 result。切「矩陣」看同一套怎麼算費氏數 F(13)。紫色=目前處理的位元。按「下一步」。
從快速冪遞迴 / 迭代、模冪,到矩陣乘法、矩陣快速冪、費氏數、通用線性遞迴,再到內建 pow、應用與小結。
❌ 模冪忘了每步取模 —— 只在最後 % m,中間的數會爆成天文數字(Python 不溢位但變慢;C++/Java 直接溢位算錯)。每次乘完就取模。
❌ 沒處理 n = 0 —— a⁰ = 1、M⁰ = 單位矩陣。迴圈版剛好回傳初始的 1 / 單位矩陣,遞迴版要記得 base case。
❌ 矩陣乘法當成可交換 —— A·B ≠ B·A。快速冪裡 result 乘 base 的順序要一致,弄反可能算錯。
❌ 遞迴費氏數 O(2ⁿ) —— 樸素 fib(n)=fib(n-1)+fib(n-2) 會指數爆炸。要快用矩陣快速冪 O(log n)(或 DP O(n))。
3¹³ 一共把 base 乘進 result 幾次?為什麼是這個次數(而不是 12 次)?13 = 1101₂,快速冪在哪幾位把 base 乘進 result?為什麼跳過第 1 位?M = [[1,1],[1,0]],為什麼 Mⁿ 裡就藏著 F(n)?任何線性遞迴都能這樣做嗎?把答案打到對話裡,我幫你對。