快速幂原理|曾子愚 's Blog

快速幂算法旨在高效计算 $a^b \mod m$ 。其核心思想是利用指数的二进制表示，将乘法次数减少到 $O(\log b)$ 级别。详细解释如下：

快速幂的思想

给定计算 $a^b \mod m$ ，如果 $b$ 表示为二进制数（如 $b = 13_{10} = 1101_2$ ），那么我们可以将其表示为：

a^{13} = a^{2^3} \cdot a^{2^2} \cdot a^{2^0}

这等价于：

a^{13} = a^8 \cdot a^4 \cdot a^1

代码逻辑逐步解释

long long mod_pow(long long a, long long b, long long m) {
    long long result = 1;  // 初始化结果为1，因为任何数的0次幂都是1。
    a = a % m;             // 确保a < m，避免不必要的大数计算。

    while (b > 0) {        // 当指数b大于0时，继续循环。
        if (b % 2 == 1) {  // 如果b是奇数，当前位是1，将a的当前幂次乘入结果。
            result = (result * a) % m;
        }
        a = (a * a) % m;   // 平方a，使其变为a的下一个2的幂次。
        b /= 2;            // 将b右移一位（相当于除以2），处理下一个二进制位。
    }
    return result;         // 返回最终结果。
}

为什么只在 `b % 2 == 1` 时才乘 `a`？

我们需要在 b 的二进制表示中，所有为 1 的位所对应的 $a^{2^i}$ 累乘到 result。
如果 b 的当前位是 1（即 b % 2 == 1），这意味着 $a^{2^i}$ 是构成 $a^b$ 所需的一个因子，因此要将 a 累乘到 result。
如果 b 的当前位是 0，说明 $a^{2^i}$ 不需要参与乘积，因此跳过。

为什么在 `return result;` 时不乘 `a`？

在 while 循环中，result 已经累积了所有需要的 $a^{2^i}$ 的乘积。
a 已在每次迭代中通过 a = (a * a) % m 更新，用于计算更高次的幂，但只有当对应的 b 的二进制位为 1 时，才将其乘入 result。
退出循环时，b 已经被右移到 0（即已经处理完所有二进制位），result 就是完整的乘积。
如果在 return 时再乘以 a，会导致额外的乘积，结果会错误，因为 a 在最后一次迭代中已经被平方或更新到一个更高次的幂。