已知a % m，如何高效计算(a^x) % m？

当然有！你目前用的逐次递归相乘取模的方法，时间复杂度是O(x)——当x是个很大的数值（比如百万、千万级）时，效率会变得很低。更高效的解决方案是快速幂（模幂运算），它的时间复杂度仅为O(log₂x)，能大幅减少计算次数，尤其适合大指数场景。

快速幂的核心原理 #

快速幂利用了指数的二进制分解特性：任何正整数x都能拆成若干个2的幂次之和，比如x=5（二进制101）可以写成4+1=2²+2⁰。对应的，a^x就转化为a^(2²) * a^(2⁰)。计算时，我们不断对底数平方取模，同时根据指数的二进制位是否为1，决定是否将当前底数乘入结果，每一步都保留模m的结果，避免数值过度膨胀。

结合你的例子演示 #

以a=6，m=4，x=3为例：

1. 初始值：result=1，base = a%m = 6%4=2，x=3（二进制11）
2. 第一次循环：x是奇数（二进制最后一位为1），所以result = (result * base) % m = (1*2)%4=2；接着base=(base*base)%m=(2*2)%4=0；x整除2变为1
3. 第二次循环：x仍是奇数，result=(2*0)%4=0；base=(0*0)%4=0；x整除2变为0，循环结束
4. 最终结果是0，和你递归方法得到的结果一致，但只进行了2次循环（递归需要3次相乘）

代码实现（迭代版） #

用Python写一个通用的快速幂函数：

def fast_mod_pow(a, x, m):
    result = 1
    base = a % m  # 先对底数取模，减少后续计算量
    while x > 0:
        # 如果指数当前位是1，将当前底数乘入结果
        if x % 2 == 1:
            result = (result * base) % m
        # 底数平方并取模
        base = (base * base) % m
        # 指数右移一位（等价于整除2）
        x = x // 2
    return result

为什么快速幂更优？ #

• 计算次数大幅减少：比如x=1024时，普通方法需要乘1024次，而快速幂只需要循环10次（因为log₂1024=10）
• 避免大数溢出：每一步都对中间结果取模，即使在强类型语言（如C++）中，也不会出现数值过大导致的溢出问题
• 内存占用更低：迭代版快速幂不需要递归调用栈，不会出现递归深度过大导致的栈溢出问题

内容的提问来源于stack exchange，提问作者Bharat