快速幂原理

快速幂算法旨在高效计算 $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 在最后一次迭代中已经被平方或更新到一个更高次的幂。

举例

计算 $a^{13} \mod m$：

1. b = 13_{10} = 1101_2，即 $13 = 8 + 4 + 1$。
2. 初始化 result = 1。
3. 迭代1（b 最低位是1）：result = (result * a) % m，更新 a = a^2 \mod m，b 右移。
4. 迭代2（b 当前位是0）：不更新 result，仅更新 a = a^4 \mod m，b 右移。
5. 迭代3（b 当前位是1）：result = (result * a) % m，更新 a = a^8 \mod m，b 右移。
6. 迭代4（b 当前位是1）：result = (result * a) % m，更新 a = a^{16} \mod m，b 右移。
7. b 变为0，循环结束，返回 result。

最终，result 累积了 $a^{8} \cdot a^{4} \cdot a^{1}$，即 $a^{13} \mod m$ 的正确结果。