如何计算给定的阶乘方程？

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)]

的值大于4，因为它们的行为类似于4。

---

EDIT：显然这是费马小定理的[[显而易见（但对我来说不是很明显O：-）），y包含与上述基本相同的观察结果，以及参考文献注释中的定理。

Answer 2

使用事实

@OneLyner's answer

您只需要知道阶乘模4。
显然，pow(x, k, 10) = pow(x % 10, 1 + (k-1) % 4, 10)
，这应该使您的生活更轻松。