计算 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：序列为 12：序列为 2, 4, 8, 63：序列为 3, 9, 7, 14：顺序是4、65：序列为 56：序列为 67：序列为 7, 9, 3, 18：序列为 8、4、2、69：序列为 9、10：序列为 0我认为计算整体最后一位数字的最简单方法是向后计算列表并一次计算每个计算的最后一位数字，直到我回到开始，但我不知道如何做到这一点？如果有人可以帮助或建议另一种与此相同或更有效的方法，我们将不胜感激。到目前为止我有这个代码，但它不适用于非常大的数字

Answer 1

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 2

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)

Answer 3

这更像是数学而不是编程。请注意，您列出的所有序列的长度都是 1、2 或 4。更准确地说，x^4始终以 或 结尾0, 1, 5, 6， 也是x^(4k)。所以如果你知道x^(m mod 4) mod 10，你就知道x^m mod 10。

现在，计算x2^(x3^(...^xn)) mod 4. 故事非常相似，x^2 mod 4是以太0如果x=2k或1如果x=2k+1（为什么？）。所以

1. 如果 x2 == 0，则为 0

2. 如果 x2 > 0 且 x3 == 0，则为 1

3. 如果x2是偶数，则它是2or 或0with2仅在 时发生x2 mod 4 == 2 and (x3==1 or (any x4,...xn == 0) )。

4. ifx2是奇数，那么x2^2 mod 4 == 1，所以我们得到1ifx3是偶数 else x2 mod 4。

足够的数学，让我们谈谈编码。可能有我没有涵盖的极端情况，但它应该适用于大多数情况。

def last_digit(lst):

    if len(lst) == 0:

        return 1

    x = lst[0] % 10

    if len(lst) == 1:

        return x

    # these number never change

    if x in [0,1,5,6]:

        return x

    # now we care for x[1] ^ 4:

    x1 = x[1] % 4

    # only x[0] and x[1]

    if len(lst) == 2 or x1==0:

        return x[0] ** x1 % 10

    # now that x[2] comes to the picture

    if x1 % 2: # == 1

        x1_pow_x2 = x1 if (x[2]%2) else 1

    else: 

        x1_pow_x2 = 2 if (x1==2 and x[2]%2 == 1) else 0

    # we almost done:

    ret = x ** x1_pow_x2 % 10

    # now, there's a catch here, if x[1]^(x[2]^...^x[n-1]) >= 4, 

    # we need to multiply ret with the last digit of x ** 4

    if x[1] >=4 or (x[1] > 1 and x[2] > 1):

        ret = (ret * x**4) % 10

    return ret