在Python中计算数字阶乘最右边非零数字的高效算法

Question

高效计算 n 阶乘最右边的非零数字

我想计算给定数字的阶乘的最右边的数字并打印它。到目前为止我所做的是：

import math
n = int(input())
fact = math.factorial(n)
print(str(fact).rstrip('0')[-1])

但我仍然受到时间限制，我寻找更快的解决方案。值得注意的是，我必须使用python来解决这个问题。
另外，我要指出的是，n是从1到65536，时间限制是0.5秒，并且我有256兆字节的内存。

Answer 1

您可以使用一个简洁的递归公式：令 D(n) 为 n 中的最后一个非零数字！

• 如果n<10，则使用查找表
• 如果n的倒数第二位是奇数，则D(n) = 4 * D(n//5) * D(n的个位数)
• 如果n的倒数第二位是偶数，则D(n) = 6 * D(n//5) * D(n的个位数)

请参阅这篇数学 stackexchange 帖子以获取证明。

将其翻译成代码：

def last_nonzero_factorial_digit(n):
    lookup = [1, 1, 2, 6, 4, 2, 2, 4, 2, 8]
    if n < 10:
        return lookup[n]

    if ((n // 10) % 10) % 2 == 0:
        return (6 * last_nonzero_factorial_digit(n // 5) * lookup[n % 10]) % 10
    else:
        return (4 * last_nonzero_factorial_digit(n // 5) * lookup[n % 10]) % 10

在我的笔记本电脑上，该版本在 5 位数字上的运行速度快了约 14,000 倍。