python - 如何计算给定的大数阶乘方程？

Question

如何找到 X^(N!) 的最后一位数字？

X 可以达到 10^9

N 可以达到 10^18

当只有其中一个很大但两个都不是时，我知道该怎么做。

ps:执行时间为1秒

Answer 1

我没有这方面的证据但是...

假设我们的目标函数是:

import math


def pow_fact_mod_last_digit_exact(x, y):
    return pow(x, math.factorial(y), 10)

但对于 x 的大值和 y这会花费太长时间。

这实际上等同于:

import math


def pow_fact_mod_last_digit(x, y):
    return pow(x, math.factorial(min(y, 4)), 10)

测试前几百个数字:

print(all(
    pow_fact_mod_last_digit(x, y) == pow_fact_mod_last_digit_exact(x, y)
    for x in range(-300, 300) for y in range(300)))
# True

---

我是怎么做到的(凭经验)

让我们看看如何pow(x, y, 10)对 x 的某些值表现和 y :

n = 20  # x
m = 24  # y
print(f'{"":2s}', end=' ')
for y in range(m):
    print(f'{y:2d}', end=' ')
print()
for x in range(n):
    print(f'{x:2d}', end=' ')
    for y in range(m):
        print(f'{pow(x, y, 10):2d}', end=' ')
    print()

    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 
 0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 2  1  2  4  8  6  2  4  8  6  2  4  8  6  2  4  8  6  2  4  8  6  2  4  8 
 3  1  3  9  7  1  3  9  7  1  3  9  7  1  3  9  7  1  3  9  7  1  3  9  7 
 4  1  4  6  4  6  4  6  4  6  4  6  4  6  4  6  4  6  4  6  4  6  4  6  4 
 5  1  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5 
 6  1  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6 
 7  1  7  9  3  1  7  9  3  1  7  9  3  1  7  9  3  1  7  9  3  1  7  9  3 
 8  1  8  4  2  6  8  4  2  6  8  4  2  6  8  4  2  6  8  4  2  6  8  4  2 
 9  1  9  1  9  1  9  1  9  1  9  1  9  1  9  1  9  1  9  1  9  1  9  1  9 
10  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
11  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
12  1  2  4  8  6  2  4  8  6  2  4  8  6  2  4  8  6  2  4  8  6  2  4  8 
13  1  3  9  7  1  3  9  7  1  3  9  7  1  3  9  7  1  3  9  7  1  3  9  7 
14  1  4  6  4  6  4  6  4  6  4  6  4  6  4  6  4  6  4  6  4  6  4  6  4 
15  1  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5 
16  1  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6 
17  1  7  9  3  1  7  9  3  1  7  9  3  1  7  9  3  1  7  9  3  1  7  9  3 
18  1  8  4  2  6  8  4  2  6  8  4  2  6  8  4  2  6  8  4  2  6  8  4  2 
19  1  9  1  9  1  9  1  9  1  9  1  9  1  9  1  9  1  9  1  9  1  9  1  9 

所以，它看起来像得到pow(x, y, 10)你只需要你只需要知道x % 10 (当然)和(y - 1) % 4 .

现在，一个数的阶乘 factorial(n) % k是0对于 n > k我们最多只需要注意 n <= k 的情况.

以k = 4为例，我们有:

import math


print([(i, math.factorial(i) % 4) for i in range(10)])
# [(0, 1), (1, 1), (2, 2), (3, 2), (4, 0), (5, 0), (6, 0), (7, 0), (8, 0), (9, 0)]

所以我们不需要担心 y 的值高于 4，因为它们的行为类似于 4。

---

编辑:显然这显而易见来自费马小定理(但对我来说并不明显 O:-))和 @OneLyner's answer包含与上述基本相同的观察结果，以及评论中对定理的引用。