快速冪算法的基礎和擴展

快速冪

快速冪（Fast Exponentiation）算法解決這樣一個問題：求解自然數的指數運算。計算 $a^b$ 時，按照指數定義的樸素的方法是通過連續相乘：

\[a^b = \underbrace{a \times a \times \cdots \times a}_{b\text{次}} \]

這種方法需要進行 $b-1$ 次乘法，當 $b$ 很大時（如 $10^9$），時間復雜度 $O(b)$ 是完全不可接受的。

快速冪通過巧妙的二進制分解技術，將冪運算的時間復雜度從 $O(b)$ 優化到 $O(\log b)$。

考慮計算 $a^{13}$，將指數 13 用二進制表示：

\[13 = 1101_2 = 2^3 + 2^2 + 0 + 2^0 = 8 + 4 + 0 + 1 \]

因此：

\[a^{13} = a^{8 + 4 + 0 + 1} = a^8 \times a^4 \times a^0 \times a^1 \]

而 $ a^8 = (a^4) ^2 = ((a^2) ^2) ^2$ ，分解后的冪次很容易計算

算法流程：

初始化結果 1
從最低位開始檢查指數的二進制位
如果當前位為 1，將當前的底數（$a^{2^x}$）乘入結果
底數不斷平方（不斷計算 $a^0,a^1,a^2...$），指數右移一位
重復直到指數的最高位 1 也被遍歷

快速冪算法也可以從遞歸的角度來理解，這種理解方式更加直觀。

\[a^b = \begin{cases} 1 & \text{if } b = 0 \\ (a^{b/2})^2 & \text{if } b \text{ is even} \\ a \times (a^{(b-1)/2})^2 & \text{if } b \text{ is odd} \end{cases} \]

long long quick_pow(long long base, long long exp) {
    long long res = 1;
    while (exp) {
        if (exp & 1) {
            res *= base;
        }
        base *= base;
        exp >>= 1;
    }
    return res;
}

帶模數版本

更多的時候，我們要求解的是 $a^b \bmod m$。這也可以用快速冪思想解決。快速冪模數版本的正確性基于模運算的分配律：

\[(a \times b)\bmod m = [(a \bmod m) \times (b \bmod m)] \bmod m \]

因此，我們可以直接對 $ a $ 取模，同時在算法每一步中，我們都對中間結果取模，這保證了最終結果的正確性，同時防止數值溢出。

不過我們不能直接對指數取模。指數 $b$ 必須保持原值，因為：

\[a^b \bmod m \neq a^{b \bmod m} \bmod m \]

當然，既然復雜度是對數的，所以 $b$ 大一些一般也無所謂。

long long quick_pow(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;  // 先取模，防止初始base過大
    while (exp) {
        if (exp & 1) {
            res = (res * base) % mod;
        }
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

不過，在某些特定情況下，我們可以使用歐拉定理來化簡指數：

歐拉定理：如果 $a$ 和 $m$ 互質（即 $\gcd(a, m) = 1$），那么：

\[a^{\phi(m)} \equiv 1 \pmod{m} \]

其中 $\phi(m)$ 是歐拉函數，表示小于 $m$ 且與 $m$ 互質的正整數的個數。

所以當 $a$ 和 $m$ 互質時，我們可以將指數對 $\phi(m)$ 取模：

\[a^b \mod m = a^{b \mod \phi(m)} \mod m \]

這在某些數學和密碼學應用中很有用，但不是快速冪算法的必要部分。代碼略。

快速冪方法的時間復雜度是 $O(\log b)$，循環次數等于指數的二進制位數，效率極高。

演示：計算 $3^{13} \mod 100$

指數 13 = 1101(二進制)
初始化: res = 1, base = 3

第1輪 (最低位為1): res = 1×3 = 3, base = 32 = 9
第2輪 (位為0):    res = 3,     base = 92 = 81  
第3輪 (位為1):    res = 3×81 = 243 ≡ 43, base = 812 = 6561 ≡ 61
第4輪 (位為1):    res = 43×61 = 2623 ≡ 23

結果: 313 ≡ 23 (mod 100)

快速乘（防治溢出）

同樣的思想也可以應用到乘法本身中。兩個 32 位整數相乘，范圍將達到 64 位；兩個 64 位整數相乘，范圍將達到 128 位。同樣大小的數無法裝入正確的結果。

快速乘（又稱"龜速乘"）模仿快速冪的思想，將乘法運算轉換為加法運算。核心思路是將 $a \times b$ 看作是 $b$ 個 $a$ 相加，然后利用二進制分解來優化，這樣就可以在中間結果下取模。

對于 $a \times b$，將 $b$ 二進制分解：

\[b = \sum_{i=0}^{k} b_i \cdot 2^i \quad \text{其中 } b_i \in \{0,1\} \]

那么：

\[a \times b = a \times \sum_{i=0}^{k} b_i \cdot 2^i = \sum_{i=0}^{k} b_i \cdot (a \cdot 2^i) \]

typedef long long ll;

// 快速乘：返回 (a * b) % mod，防止中間過程溢出
ll quick_mul(ll a, ll b, ll mod) {
    ll res = 0;
    a %= mod;
    while (b) {
        if (b & 1) {
            res = (res + a) % mod;
        }
        a = (a + a) % mod;  // a = 2a，相當于左移一位
        b >>= 1;
    }
    return res;
}

// 使用快速乘的快速冪
ll quick_pow_safe(ll base, ll exp, ll mod) {
    ll res = 1;
    base %= mod;
    while (exp) {
        if (exp & 1) {
            res = quick_mul(res, base, mod);  // 關鍵替換！
        }
        base = quick_mul(base, base, mod);    // 關鍵替換！
        exp >>= 1;
    }
    return res;
}

方法	時間復雜度	空間復雜度	防溢出能力
直接乘法	$O(1)$	$O(1)$	無
快速乘	$O(\log n)$	$O(1)$	有

快速乘通過 $O(\log n)$ 次加法替代 $O(1)$ 次乘法，實際上更慢了，所以也叫做“龜速乘”，這屬于用時間換取了數值安全性。

浮點冪

如果是底數浮點，指數自然數，那么直接應用快速冪沒有任何問題。但若指數是浮點數，這個問題會麻煩的多：浮點數指數無法直接進行二進制位操作，且誤差會隨著運算的拆分不斷累積。

相比之下浮點冪的主要思想是利用自然對數變換法來計算浮點冪：

\[a^b = e^{b \cdot \ln(a)} \]

其中，自然對數和指數是常見且重要的函數，有快速且精確的辦法來實現。

常見的庫（如C++ <cmath>、Intel MKL、GNU Scientific Library）采用此類核心思路。

// 偽代碼示意
if (a == 0.0) {
    if (b > 0) return 0.0;
    if (b == 0) return 1.0;  // 或 NaN，依標準而定
    return INFINITY;         // 或報錯
}
if (a == 1.0) return 1.0;
if (b == 0.0) return 1.0;
if (b == 1.0) return a;

result = exp(b * log(a)); # 對于一般情況

矩陣快速冪

已知矩陣 $A$，由于矩陣乘法滿足結合律，指數為自然數時，仍可以利用快速冪思想求解 $A^n$。這最其深刻、最實用的擴展之一。它將快速冪的核心理念從標量運算成功遷移到了線性代數領域。

\[A^n = \begin{cases} I & \text{if } n = 0 \\ (A^{n/2})^2 & \text{if } n \text{ is even} \\ A \times (A^{(n-1)/2})^2 & \text{if } n \text{ is odd} \end{cases}\]

typedef vector<vector<long long>> Matrix;

Matrix matrixMultiply(const Matrix& A, const Matrix& B, long long mod) {
    int n = A.size();
    Matrix C(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
            }
        }
    }
    return C;
}

Matrix matrixPow(Matrix base, long long exp, long long mod) {
    int n = base.size();
    // 初始化單位矩陣
    Matrix res(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) {
        res[i][i] = 1;
    }
    
    while (exp > 0) {
        if (exp & 1) {
            res = matrixMultiply(res, base, mod);
        }
        base = matrixMultiply(base, base, mod);
        exp >>= 1;
    }
    return res;
}

經典案例：斐波那契數列的矩陣解法

斐波那契數列的遞推關系：

\[F(n) = F(n-1) + F(n-2) \]

可以表示為矩陣形式：

\[\begin{bmatrix} F(n) \\ F(n-1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} F(n-1) \\ F(n-2) \end{bmatrix}\]

遞推得到：

\[\begin{bmatrix} F(n) \\ F(n-1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1} \times \begin{bmatrix} F(1) \\ F(0) \end{bmatrix}\]

由于我們可以快速計算矩陣的冪，我們就繞過了斐波那契數列的定義，使用對數次矩陣乘法的時間直接計算出了某一項。

long long fibonacci_matrix(long long n, long long mod) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    Matrix base = {{1, 1}, {1, 0}};
    Matrix result = matrixPow(base, n - 1, mod);
    return result[0][0];  // F(n)
}

更一般的，對于 k 階線性遞推：

\[a_n = c_1a_{n-1} + c_2a_{n-2} + \cdots + c_ka_{n-k} \]

構造轉移矩陣：

\[M = \begin{bmatrix} c_1 & c_2 & \cdots & c_{k-1} & c_k \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{bmatrix}\]

則：

\[\begin{bmatrix} a_n \\ a_{n-1} \\ \vdots \\ a_{n-k+1} \end{bmatrix} = M^{n-k+1} \times \begin{bmatrix} a_{k-1} \\ a_{k-2} \\ \vdots \\ a_0 \end{bmatrix}\]

posted @ 2025-10-03 15:21 Ofnoname 閱讀(241) 評論(0) 收藏舉報

刷新頁面返回頂部

方法	時間復雜度	空間復雜度	防溢出能力
直接乘法	\(O(1)\)	\(O(1)\)	無
快速乘	\(O(\log n)\)	\(O(1)\)	有

Ofnoname

萬水千山只等閑

快速冪算法的基礎和擴展

快速冪

帶模數版本

快速乘（防治溢出）

浮點冪

矩陣快速冪

經典案例：斐波那契數列的矩陣解法