python - 计算x1 ^(x2 ^(x3 ^(... ^ xn)))的最后一位(十进制)

This question already has answers here:

Last digit of power list

(3个答案)


2年前关闭。




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

我尝试了几种方法，但我认为解决此问题的最佳方法是使用序列。例如，任何以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

最佳答案

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)

关于python - 计算x1 ^(x2 ^(x3 ^(... ^ xn)))的最后一位(十进制)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53960629/