一. 快速幂算法的原理
快速幂算法是一种用于求解 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 取模的结果。
八. 快速幂算法的作用
快速幂算法在计算大数字模幂运算时非常有用，它可以大大缩短计算时间，减少计算复杂度。
比如在密码学、编码、组合数学等领域的计算中，快速幂算法都有广泛应用。
