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

<分区>

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

我尝试了几种方法，但我认为解决这个问题的最佳方法是使用序列。例如，任何以 1 结尾的数字，在求幂时，总是以 1 结尾。对于 2，结果数字将以 2、4、6 或 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。然后我们可以通过将 4 添加到 n 来防止 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/

上一篇：python - PyCharm 无法在同一文件夹中找到导入

下一篇：Python:猴子修补函数的源代码

相关文章：

python - 用于匹配标题和子标题的正则表达式，后跟项目符号列表

.net - 为什么我的 .net Int6 4's behaves as if they were Int32' s？

java - 如何使用递归计算幂的幂？

math - Prolog 常见差异，多项式序列中的下一个数字

algorithm - 最接近某个值的公约数的近似值？

python - 带模数的 Numpy 矩阵幂/指数？

javascript - 电源列表的最后一位

python - 在 pandas 数据框中查找每行的两个列列表中哪一个是真的最快方法

python - 你能推荐一个好的 minhash 实现吗？

variables - "Pythonic"到 "reset"一个对象的变量？