如何优化递推乘法算法并利用模运算求解arr[249]%169？

核心优化思路：每步取模 #

递推式的数值增长呈指数级，但模运算满足以下关键性质，可在每一步计算时截断数值：
(a + b * c) % m = [(a % m) + ((b % m) * (c % m)) % m] % m
通过每一步对169取模，能避免数值过大导致的计算缓慢和内存占用问题，同时保证最终结果的正确性。

优化后的迭代实现 #

原循环代码逻辑正确，但缺少模运算处理。修改后的高效实现如下：

def optimized_loop(n, mod=169):
    if n == 1:
        return 1 % mod
    elif n == 2:
        return 2 % mod
    elif n == 3:
        return 3 % mod
    # 用三个变量存储前三项，替代数组操作更高效
    prev3, prev2, prev1 = 1, 2, 3
    for _ in range(4, n + 1):
        current = (prev3 + prev2 * prev1) % mod
        prev3, prev2, prev1 = prev2, prev1, current
    return prev1

# 计算arr[249] % 169
print(optimized_loop(249))

代码说明： #

• 用三个变量替代数组，减少内存开销和数组操作的时间损耗
• 每一步计算时直接对169取模，确保数值始终维持在0-168的范围内
• 时间复杂度为O(n)，空间复杂度为O(1)，针对n=249的计算可瞬间完成

为什么递归方法不适用？ #

原递归方法存在大量重复计算（例如计算recursion(6)时，recursion(4)会被重复调用两次），n越大重复计算量呈指数级增长。即使添加记忆化缓存，其效率也远低于迭代法，且实现复杂度更高。

正确性验证 #

用原测试用例验证优化后的代码：

• optimized_loop(6)返回164，与原代码计算结果一致
• optimized_loop(4)返回7，optimized_loop(5)返回23，均符合递推公式的计算结果

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