如何优化多层幂运算末位数字求解算法的运行效率？

你的核心问题是直接计算超大幂值导致性能爆炸，我们可以利用模运算性质和欧拉定理彻底规避大数计算，大幅提升效率。

原代码的问题 #

直接计算lst[i] ** temp会生成天文数字级的中间值，不仅计算耗时极长，还可能触发内存溢出。实际上我们只需要末位数字（即模10的结果），完全不需要计算完整的幂值。

优化思路 #

利用以下数学性质简化计算：

1. 欧拉定理：对于整数a和m，若a与m互质，则a^b ≡ a^(b mod φ(m)) mod m；若不互质且b ≥ φ(m)，则a^b ≡ a^(b mod φ(m) + φ(m)) mod m（φ(m)是欧拉函数，表示小于m且与m互质的正整数个数）。
2. 末位循环周期：数字的幂次末位存在固定周期（如2的幂末位周期为4，4的幂末位周期为2），结合欧拉定理可快速缩小指数规模。

优化后的代码 #

import math

def last_digit(lst):
    def euler_phi(n):
        # 针对我们需要的小数值直接返回，避免通用计算的开销
        if n == 1:
            return 1
        elif n == 2:
            return 1
        elif n == 4:
            return 2
        elif n == 5:
            return 4
        elif n == 10:
            return 4
        # 通用欧拉函数计算（可选扩展）
        res = n
        i = 2
        while i * i <= n:
            if n % i == 0:
                while n % i == 0:
                    n //= i
                res -= res // i
            i += 1
        if n > 1:
            res -= res // n
        return res

    def helper(lst, mod):
        if mod == 1:
            return (0, True)
        if not lst:
            return (1, 1 >= mod)
        if len(lst) == 1:
            val = lst[0]
            return (val % mod, val >= mod)
        
        a = lst[0]
        rest = lst[1:]
        phi = euler_phi(mod)
        exp_mod_phi, exp_ge_phi = helper(rest, phi)

        # 确定用于计算的指数
        gcd_val = math.gcd(a, mod)
        if gcd_val == 1:
            exp = exp_mod_phi
        else:
            exp = exp_mod_phi + phi if exp_ge_phi else exp_mod_phi

        # 处理0^0的特殊情况（按问题定义返回1）
        if a == 0 and exp == 0:
            val_mod = 1
        else:
            val_mod = pow(a, exp, mod)
        
        # 判断当前幂值是否大于等于mod（用于上层计算）
        if a == 0:
            is_ge = (exp == 0 and 1 >= mod) or (exp > 0 and 0 >= mod)
        elif a == 1:
            is_ge = 1 >= mod
        else:
            if exp == 0:
                is_ge = 1 >= mod
            elif exp == 1:
                is_ge = a >= mod
            else:
                is_ge = (a ** exp) >= mod
        
        return (val_mod, is_ge)

    if not lst:
        return 1
    res_mod, _ = helper(lst, 10)
    return res_mod

代码说明 #

1. 欧拉函数实现：针对我们需要的小模数（1、2、4、5、10）直接返回结果，减少计算开销。
2. 递归辅助函数：
   • 每次递归计算多层幂的模值，同时返回该幂值是否大于等于当前模数（用于判断是否需要在指数中加上欧拉函数值）。
   • 利用pow(a, exp, mod)直接计算模幂，这是Python内置的高效实现，不会生成大数。
3. 特殊情况处理：覆盖空列表、0^0、底数为0/1等边界场景，确保结果正确。

性能对比 #

• 原代码计算[2, 10**100000]会陷入长时间计算甚至崩溃；
• 优化后的代码可在毫秒级返回结果（末位为6）。

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