如何快速计算2^(a^b)的最后三位数字 Python实现优化问题

你当前的代码卡顿甚至无法运行的核心原因是：当a、b增大时，a ** b的结果会指数级暴涨，比如8**8 = 16777216，此时计算2 ** 16777216会得到一个近500万位的超级大数，不管是存储这个大数还是把它转成字符串处理，开销都会爆炸，完全没有必要。

求一个数的最后三位，等价于求这个数对1000取模的结果，我们可以直接通过模运算的性质完成计算，不需要算出表达式的完整值：

• 模幂运算性质：(x ^ y) % m 可以通过快速模幂算法直接计算，全程不需要生成x^y的完整大数
• Python内置的三参数pow(base, exp, mod)函数底层实现了高效的快速模幂，哪怕指数极大也能秒出结果

如果你的输入a、b不会大到a**b本身无法计算的程度，最简写法如下，输入(100,100)都可以秒出结果：

def last_three(a, b):
    return pow(2, pow(a, b), 1000)

如果需要适配a、b极大（比如a=1000，b=1000，此时a**b本身就是超大数）的场景，可以用欧拉定理进一步简化指数计算：

def last_three(a, b):
    k = pow(a, b)
    if k < 3:
        return pow(2, k)
    # φ(1000)=400，2和1000不互质，指数>=3时补充偏移兼容模8的情况
    exp = k % 400
    exp = 400 if exp == 0 else exp
    return pow(2, exp, 1000)

上述代码和你原有逻辑的输出完全一致，但性能提升了数个量级，不会再出现卡顿、无法运行的问题。

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