巨数的最后一位Python

Question

我正在尝试解决

x1 ^ (x2 ^ (x3 ^ (... ^ xn)))

，其中 x1、x2 等是给定列表 lst 中的数字，并且该函数将返回结果的最后一位数字。

例如，如果 lst = [3, 4, 5]，则应返回 1
另一个例子，如果 lst = [499942, 898102, 846073]，它应该返回 6

我的代码已成功通过了 600 多个随机列表的测试，从最小到我认为最长为 6 位数字，但在这两个列表上失败了：

[2, 2, 101, 2], [12, 30, 21]

def last_digit(lst):
    result = 1
    for num in reversed(lst):
        result = pow(num, result, 100)
    print(lst)
    return result%10

Answer 1

你走在正确的轨道上，它可以适用于很多情况，但有一个小问题。看到您正在尝试计算幂序列的最后一位数字。问题在于如何减少中间结果；您当前正在以 100 为模减少每个中间结果，这可能并不总能给出正确的最后一位数字。

这里，您需要将每个中间结果减少模 10 而不是 100。这是修改后的版本：

def last_digit(lst):
    result = 1
    for num in reversed(lst):
        result = num ** (result % 4 + 4)   
        # Reducing result modulo 4 and add 4 for optimisation
    return result % 10

首先在循环中看到，为了优化目的，我们计算结果模 4 并加 4。这一步确保我们始终使用正指数，从而简化了计算。最后，我们将结果模 10 得到最后一位数字。

它应该正确处理您的测试用例，包括那些以前失败的测试用例。如果您需要任何其他帮助，请告诉我。