快速幂算法详解

一. 快速幂算法的原理

快速幂算法是一种用于求解 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 取模的结果。

八. 快速幂算法的作用

快速幂算法在计算大数字模幂运算时非常有用，它可以大大缩短计算时间，减少计算复杂度。

比如在密码学、编码、组合数学等领域的计算中，快速幂算法都有广泛应用。