快速冪演算法詳解

一. 快速冪演算法的原理

快速冪演算法是一種用於求解 a^b % m 的演算法，其中 a、b、m 都是正整數，b 可能非常大。如果直接計算 a^b % m，需要計算 b 次乘法，這樣的時間複雜度顯然很高。快速冪演算法通過將指數 b 轉化為二進位形式，可以只進行 log(b) 次乘法，從而大大減少計算時間。

二. 快速冪演算法的步驟

快速冪演算法的步驟如下：

1. 將指數 b 轉化為二進位形式。

2. 從高位到低位遍歷二進位數，對於每一位：

a. 若該二進位位為 1，則乘上 a^{2^i} 並對 m 取模。

b. 將 a 平方並對 m 取模，得到 a^{2^(i+1)} mod m。

3. 遍歷結束後，得到結果 a^b mod m。

三. 快速冪演算法的 C 語言實現

unsigned long long PowMod(unsigned long long a, unsigned long long b, unsigned long long m)
{
    unsigned long long ans = 1 % m;
    a %= m;
    while (b)
    {
        if (b & 1)
        {
            ans = ans * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    return ans;
}

四. 快速模冪演算法

快速模冪演算法是快速冪演算法的一個變種，用於求解 a^b mod m，其中 a、b、m 都是正整數，b 可能非常大。其基本思路是將每一次取模放到指數的每一位上，避免了在最後一次計算時需要進行一次大的取模運算。

具體步驟如下：

1. 將指數 b 轉化為二進位形式。

2. 從高位到低位遍歷二進位數，對於每一位：

a. 將 a 對 m 取模，得到 a1。

b. 若該二進位位為 1，則乘上 a1^{2^i} 並對 m 取模，得到 a2。

3. 遍歷結束後，得到結果 a2 mod m。

五. 快速冪取模演算法

快速冪取模演算法是用於解決 a^b mod m 的值的演算法。相對於一般的演算法，它在編寫上更加簡單，更加符合運算。它的主要思想是模數m很小，可以將 a^b 不斷拆分，直到循環到 m 的範圍內。

具體步驟如下：

1. 將指數 b 轉化為二進位形式。

2. 從高位到低位遍歷二進位數，對於每一位：

a. 若該二進位位為 1，則記錄計算的結果。

b. 將 a 的值對 m 取模，然後平方，對 m 取模。

3. 遍歷結束後，將計算結果相信遇到的所有因子乘在一起，並對 m 取模。

六. 快速冪演算法 Python 實現

def powMod(a: int, b: int, m: int) -> int:
    ans = 1 % m
    a %= m
    while b:
        if b & 1:
            ans = ans * a % m
        a = a * a % m
        b >>= 1
    return ans

七. 快速冪演算法例子

例如，要求 3^123456789 的值，對 1000000007 取模。

使用普通方法需要計算 123456789 次乘法，並對 1000000007 取模，這樣的時間複雜度顯然很高。

使用快速冪演算法，將指數 123456789 轉化為二進位為 111010110111100110100010101，然後只進行了 19 次乘法，得到了 376597587 對 1000000007 取模的結果。

八. 快速冪演算法的作用

快速冪演算法在計算大數字模冪運算時非常有用，它可以大大縮短計算時間，減少計算複雜度。

比如在密碼學、編碼、組合數學等領域的計算中，快速冪演算法都有廣泛應用。