如何找到 X^(N!)
的最后一位数字?
X
可以达到 10^9
N
可以达到 10^18
当只有其中一个很大但两个都不是时,我知道该怎么做。
ps:执行时间为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包含与上述基本相同的观察结果,以及评论中对定理的引用。
关于python - 如何计算给定的大数阶乘方程?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61872893/