快速冪是一種高效計算冪運算的算法，能夠將時間復雜度從樸素的 O (n) 降低到 O (log n)。本文將深入探討快速冪的原理、實現和應用場景。

一、樸素冪運算的問題

計算 a^n 最直接的方法是循環 n 次：

long long power(long long a, long long n) {long long result = 1;for (int i = 0; i < n; i++) {result *= a;}return result;
}

這種方法的時間復雜度為 O (n)，當 n 非常大時（如 10^9），計算效率極低，甚至可能超時。

二、快速冪的數學原理

快速冪的核心思想是利用指數的二進制分解。例如，計算 3^13：

1. 將指數 13 轉換為二進制：13 = 1101 (2) = 8 + 4 + 1
2. 則 3^13 = 3^(8+4+1) = 3^8 × 3^4 × 3^1

這樣，我們只需要計算 3^1, 3^2, 3^4, 3^8 這幾個值，然后將指數二進制表示中對應位為 1 的項相乘即可。

三、快速冪的遞歸實現

遞歸實現快速冪更加直觀：

long long quickPower(long long a, long long n) {if (n == 0) return 1;if (n % 2 == 1) return a * quickPower(a, n - 1);else {long long temp = quickPower(a, n / 2);return temp * temp;}
}

遞歸的思路是：

• 如果 n 為 0，返回 1
• 如果 n 為奇數，分解為 a × a^(n-1)
• 如果 n 為偶數，分解為 (a^(n/2))^2

四、快速冪的迭代實現

迭代實現更加高效，避免了遞歸帶來的函數調用開銷：

long long quickPower(long long a, long long n) {long long result = 1;while (n > 0) {if (n & 1) result *= a;  // 如果當前位為1，累乘到結果a *= a;  // 底數平方n >>= 1;  // 指數右移一位}return result;
}

迭代的核心邏輯是：

1. 初始化結果為 1
2. 循環處理指數的每一位
3. 如果當前位為 1，將當前底數乘入結果
4. 底數平方，指數右移

五、模運算下的快速冪

在實際應用中，冪運算的結果往往非常大，需要對結果取模：

long long quickPower(long long a, long long n, long long mod) {long long result = 1;a %= mod;  // 防止初始值過大while (n > 0) {if (n & 1) result = (result * a) % mod;a = (a * a) % mod;n >>= 1;}return result;
}

六、快速冪的應用場景

1. 密碼學：RSA 算法中大量使用模冪運算
2. 數論問題：如計算大指數的余數
3. 動態規劃：狀態轉移方程中可能涉及冪運算
4. 矩陣快速冪：計算遞推數列的高效方法

七、總結

快速冪算法通過利用指數的二進制分解，將冪運算的時間復雜度從 O (n) 優化到 O (log n)，是一種非常高效的算法。迭代實現避免了遞歸調用的開銷，是實際應用中的首選。在處理大數問題時，模運算下的快速冪尤為重要。