计算x1 ^的最后一个(十进制)数字(x2 ^(x3 ^(... ^ xn)))

Question

我需要找到x1 ^ (x2 ^ (x3 ^ (... ^ xn)))传递给函数的整数的单位数作为列表.例如,输入[3, 4, 2]将返回,1因为3 ^ (4 ^ 2) = 3 ^ 16 = 43046721其最后一位是1.该函数需要尽可能高效,因为显然尝试计算767456 ^ 981242不是很快.

我尝试了一些方法,但我认为解决这个问题的最佳方法是使用序列.例如,任何以a结尾的数字1,当被提升为幂时,将始终以1.因为2,结果数字将以任何一个结束2, 4, 6 or 8.如果数字被提升为幂,则结果数字的最后一位将遵循基于指数的最后一位数的模式:

1:序列为1

2:序列是2,4,8,6

3:序列是3,9,7,1

4:序列是4,6

5:序列是5

6:序列是6

7:序列是7,9,3,1

8:序列是8,4,2,6

9:序列是9,1

0:序列为0

我认为计算总体最后一位数的最简单方法是在列表中向后工作并一次计算每个计算的最后一位数,直到我回到开始但我不知道如何做到这一点？如果有人可以提供帮助或建议另一种方法,该方法可以获得同等或更高效的方法.

到目前为止我有这个代码,但它不适用于非常大的数字

def last_digit(lst):
    if lst == []:
        return 1

    total = lst[len(lst)-2] ** lst[len(lst)-1]
    for n in reversed(range(len(lst)-2)):
        total = pow(lst[n], total)

    return total%10

编辑:0 ^ 0应该假定为1

Answer 1

x^n = x^(n%4) 因为最后一位数字的周期始终为 4。

x  ^2  ^3  ^4  ^5

1   1   1   1   1
2   4   8   6   2
3   9   7   1   3
4   6   4   6   4
5   5   5   5   5
6   6   6   6   6
7   9   3   1   7
8   4   2   6   8
9   1   9   1   9

正如您所看到的，所有 9 位数字的周期都是 4，因此我们可以使用 %4 来简化计算。

如果我们这样做%4，也会有一个模式。

x  ^0  ^1  ^2  ^3  ^4  ^5  ^6  ^7  ^8  ^9
1   1   1   1   1   1   1   1   1   1   1
2   1   2   0   0   0   0   0   0   0   0
3   1   3   1   3   1   3   1   3   1   3
4   1   0   0   0   0   0   0   0   0   0
5   1   1   1   1   1   1   1   1   1   1    (all %4)
6   1   2   0   0   0   0   0   0   0   0
7   1   3   1   3   1   3   1   3   1   3
8   1   0   0   0   0   0   0   0   0   0
9   1   1   1   1   1   1   1   1   1   1

如图所示，当 n>1 时，每个 x 都有一个模式。因此，当 n>1 时，您可以看到 (x^n)%4 = (x^(n+4k))%4。然后，我们可以通过在 n 上加上 4 来防止 n=0 和 n=1 时出现的问题。这是因为，如果 (x^n)%4 = (x^(n+4k))%4，则 (x^n)%4 = (x^(n%4+4))%4 。

powers = [3, 9, 7, 1]

lastDigit = 1

for i in range(len(powers) - 1, -1, -1):
    if lastDigit == 0:
        lastDigit = 1
    elif lastDigit == 1:
        lastDigit = powers[i]
    else:
        lastDigit = powers[i]**(lastDigit%4+4)

print(lastDigit%10)