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

Question

我需要从作为列表传递给函数的整数中找到 x1 ^ (x2 ^ (x3 ^ (... ^ xn))) 的个位数。例如输入 [3, 4, 2] 将 return 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

Answer 1

这是数学而不是编程。请注意，您列出的所有序列的长度都是 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 （为什么？）。所以

如果 x2 == 0 则为 0
如果 x2 > 0 且 x3 == 0 则为 1
如果 x2 是偶数，则它是 2 或 0，而 2 仅在 x2 mod 4 == 2 and (x3==1 or (any x4,...xn == 0) ) 时出现。
如果 x2 是奇数，那么 x2^2 mod 4 == 1，所以我们得到 1 如果 x3 是偶数 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

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

根据您的序列想法并充实它，您想要创建一个可以映射所有相关序列的字典。

mapping = {}
for i in range(1, 10):
    mapping[i] = [i]
    last_digit = i
    while True:
        last_digit *= i
        last_digit = last_digit%10
        if last_digit in mapping[i]:
            break
        else:
            mapping[i].append(last_digit)

print(mapping)

这会产生输出：映射

{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]}

现在可以开始真正的逻辑了，关键要点是序列完成后模式会自行重复。因此，无论幂有多大，只要使用模并计算出它应该占据序列的哪个位置即可。

def last_digit_func(lst, mapping):
    if lst == []: #taken from OP
        return 1
    last_digit = lst[0] % 10
    if 0 in lst[1:]: #edge case 0 as a power
        return 1
    if last_digit == 0: #edge case 0 at start
        return last_digit

    for current_power in lst[1:]:
        if len(mapping[last_digit]) == 1:
            return last_digit
        ind = current_power % len(mapping[last_digit])
        ind -= 1 #zero indexing, but powers start from 1. 
        last_digit = mapping[last_digit][ind]
    return last_digit

test1 = [3, 4, 2]
print(last_digit_func(test1, mapping)) #prints 1

我通过计算 python 中的幂验证了这一点。

test2 = [767456 , 981242]
print(last_digit_func(test2, mapping)) #prints 6

我试图通过运行在 python 中验证这一点......我现在立即后悔，我的程序仍在尝试解决它。好吧:)

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

Compute the last (decimal) digit of x1 ^ (x2 ^ (x3 ^ (... ^ xn)))

python

math

exponent