python - 求大幂的个位数

Question

我需要找到大功率的最后一位数字。当我得到简单的 x^n 时，我解决了这个问题：pow(x, n, 10)。但是当我有这样的例子时我该怎么办：103171^(14394^(221515^(441792^507709)))？我注意到特定数字的循环性，但这还不够。恐怕我错过了一些重要的观点。作为我的主函数 last_digit 的输入，我得到数字列表 (lst)，比如说 [3, 4, 2] - 这意味着我需要计算 3 ^ (4 ^ 2)。我有大约 630 个测试要通过，我只能做大约 580 个（其中大部分是随机生成的）。这是我尝试过的代码：

CYCLES = {
    0 : [0, 0, 0, 0],
    1 : [1, 1, 1, 1],
    2 : [2, 4, 8, 6],
    3 : [3, 9, 7, 1],
    4 : [4, 6, 4, 6],
    5 : [5, 5, 5, 5],
    6 : [6, 6, 6, 6],
    7 : [7, 9, 3, 1],
    8 : [8, 4, 2, 6],
    9 : [9, 1, 9, 1]
}

def power_rec(lst):
    remainder = pow(lst[-2], lst[-1], 4)
    if len(lst) == 2:
        first_num = int(str(lst[0])[-1])
        second_num = int(str(lst[1])[-1]) 
        return CYCLES[first_num][second_num - 1]
    lst = lst[:-2] + [ remainder ]
    return power_rec(lst)

def last_digit(lst):
    if len(lst) == 2:
        return pow(lst[0], lst[1], 10)
    if lst == []:
        return 1
    if len(lst) == 1:
        return int(str(lst[0])[-1])
    return power_rec(lst)

例如，我无法通过输入测试：[555913, 845991, 261716, 431426, 571315, 456986, 461380, 413475] 或 [2, 2, 101, 2]。

我必须假设 0 ^ 0 = 1 并且空列表的 last_digit 等于 1。如果有任何有用的提示，我将不胜感激。

更新。 找到最短的解决方案：

def last_digit(lst):
    result = 1
    for num in lst[::-1]:
        result = pow(num, (result if result < 4 else result % 4 + 4) )

    return result % 10

标签： pythonpython-3.xmath

Answer 1

这是一道纯数学题……

任何数字的最后一位数字都是模 10 的数字。所以当它们是一个大的指数级联时，你会问如何减少模 10 的数字。

为此，您可以反复应用欧拉定理。它所说的（嗯，暗示）是为了减少 a^b 模 n，你可以减少 b 模 phi(n)。

因此，要减少 a^b 模 10，您可以从减少 b 模 phi(10) = 4 开始。

这里，b 的形式为 c^d。要减少 c^d 模 4，您可以从减少 d 模 phi(4) = 2 开始。这足以使这个问题变得简单。

让我们举个例子：

103171^(14394^(221515^(441792^507709))) 模 10

从减少 (221515^(blahblah)) 模 2 开始。这很明显是 1，所以我们已经归结为：

103171^(14394^1) = 103171^14394 模 10

接下来，只需将 14394 模 4 减为 2。所以我们只需要：

103171^2 模 10

我想你可以从那里拿走它。

（更新）

我忘记了欧拉定理只适用于 a（底）和 n（模）没有共同因子的情况。哎呀。

所以当试图减少 14394^(blahblah) 模 4 时，我们必须直接这样做...... 14394^（大幂）实际上可以被 4 整除，所以这实际上是零，正确答案是 103171^0 = 1。 （另一种方法也提供了，但只是靠运气。）

对于您评论中的示例 (7^(6^21))，我们有类似的情况。6^21 为零（模 4），所以答案是 7^0 = 1。

12^(30^21) 更棘手，因为 12 和 10 不是互质数。在这里，我们需要计算值 (mod 5) 和 (mod 2) 并将两者结合起来。但是我开会迟到了，所以我现在不能完成这个:-)