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兆字节。

- Shayan

---

我会避免创建一个字符串。 - MrSmith42

你需要处理多大的 n 值？当我尝试使用 n=100000 的方法时，几秒钟内就能得到答案。"但我仍然遇到时间限制" - 这是否意味着你正在向别人的测试程序（例如在线测试器）提供代码？在这种情况下，请务必确保你完全理解输入和输出的预期工作方式。可能是因为 input 会一直等待，因为测试器不会在 stdin 上提供输入，并且它可能不接受 print 的内容作为有效输出。请检查是否应该读取或写入文件。 - Karl Knechtel

@MrSmith42 我一开始也是这么想的，但在我的测试中，明显的绕过这个问题并没有使事情更快。 - Karl Knechtel

@Karl Knechtel；好的，我明白了，计算阶乘是错误的方法，因为我们从来不需要整个数字。 - MrSmith42

还有在codegolf stackexchange上：n!的最后一个非零数字 - Stef

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 的个位数)

请参考这个数学堆栈交换帖子进行证明。

将其转换为代码：

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

在我的笔记本电脑上，这个版本在一个五位数的数字上运行速度快了大约14,000倍。

- Seon

---

非常感谢，代码完美运行。 - Shayan

Answer 2

一个简单而又足够快速的方法，就是计算阶乘，然后移除与更为频繁的质因数2一同导致零出现的质因数5的次数相同的零（因为这就是导致零的原因）。从1到n中每隔5个数字贡献一个质因数5，每隔5个这样的质因数5又贡献一个，以此类推。

def Kelly(n):
    res = math.factorial(n)
    while n:
        n //= 5
        res //= 10**n
    return res % 10

以 n=65536 为限制进行基准测试：

0.108791 seconds  just_factorial
1.434466 seconds  Shayan_original
0.553055 seconds  Shayan_answer
0.000016 seconds  Seon
0.208012 seconds  Kelly
0.029500 seconds  Kelly2

我们发现仅计算阶乘而不提取所需数字的速度已经足够快了。只是通过字符串提取数字的原始方法较慢。

（注：楼主Shayan说他们的答案解决方案“对我有用并完成了工作”，而我的更快，这就是为什么我说我的足够快（也因为它在0.5秒以下）。看起来他们只是因为无法解释而删除了自己的答案。）

另一种简单且更快的方法：

def Kelly2(n):
    prod = 1
    twos = 0
    for i in range(2, n + 1):
        while not i % 2:
            i //= 2
            twos += 1
        while not i % 5:
            i //= 5
            twos -= 1
        prod = prod * i % 10
    return prod * pow(2, twos, 10) % 10

在这里，我们自己将数字从1乘到n。但是提取质因数2和5并分别计数。然后n！= 2^twos * 5^fives * ProductOfReducedFactors。由于2和5的成对会导致不需要的尾随零，因此请计算我们无法与5配对的2的数量。这就是我的代码所做的。然后nFactorialWithoutTrailingZeros = 2^twos * ProductOfReducedFactors。我们可以使用% 10在整个计算过程中保持ProductOfReducedFactors小，并获得其最后一位数字。

测试代码（在线尝试！）：

import math
from time import time


def just_factorial(n):
    math.factorial(n)
    return -1


def Shayan_original(n):
    fact = math.factorial(n)
    return str(fact).rstrip('0')[-1]


def Shayan_answer(n):
    a = n // 5
    b = n - 5 * a
    fact_a = math.factorial(a)
    fact_b = math.factorial(b)
    power_a = 2 ** a
    res = fact_a * fact_b * power_a
    while (res % 10 == 0):
        res //= 10
    return int(res % 10)


def Seon(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 * Seon(n // 5) * lookup[n % 10]) % 10
    else:
        return (4 * Seon(n // 5) * lookup[n % 10]) % 10


def Kelly(n):
    res = math.factorial(n)
    while n:
        n //= 5
        res //= 10**n
    return res % 10


def Kelly2(n):
    prod = 1
    twos = 0
    for i in range(2, n + 1):
        while not i % 2:
            i //= 2
            twos += 1
        while not i % 5:
            i //= 5
            twos -= 1
        prod = prod * i % 10
    return prod * pow(2, twos, 10) % 10


funcs = just_factorial, Shayan_original, Shayan_answer, Seon, Kelly, Kelly2

# Correctness
for n in *range(1001), 65536:
    expect = funcs[1](n)
    for f in funcs[2:]:
        result = str(f(n))
        assert result == expect

# Speed
for f in funcs:
    t = time()
    f(65536)
    print(f'{time() - t :8.6f} seconds ', f.__name__)

- Kelly Bundy

Answer 3

一个基于 你的回答 的解决方案（只是重复你的简化步骤），一个优化版本，击败了 Seon 的版本，以及 Seon 的优化版本。n=65536 时的时间：

  2.04 ± 0.03 μs  Seon_optimized
  2.54 ± 0.04 μs  Kelly3_optimized
  4.18 ± 0.04 μs  Seon
 20.51 ± 0.09 μs  Kelly3

代码（在线尝试！）：

def Kelly3(n):
    res = 1
    while n:
        res *= factorial(n % 5)
        n //= 5
        res <<= n
    return res % 10


def Kelly3_optimized(n):
    res = 1
    twos = 0
    while n:
        res *= (1, 1, 2, 6, 24)[n % 5]
        n //= 5
        twos += n
    shift = twos and (twos % 4 or 4)
    return (res << shift) % 10


def Seon_optimized(n):
    lookup = 1, 1, 2, 6, 4, 2, 2, 4, 2, 8
    Lookup = 6, 6, 2, 6, 4, 2, 2, 4, 2, 8, 4, 4, 8, 4, 6, 8, 8, 6, 8, 2
    res = 1
    while n >= 10:
        res *= Lookup[n % 20]
        n //= 5
    return res * lookup[n] % 10


def Seon(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 * Seon(n // 5) * lookup[n % 10]) % 10
    else:
        return (4 * Seon(n // 5) * lookup[n % 10]) % 10


from timeit import timeit
from statistics import mean, stdev
from math import factorial

funcs = Seon, Kelly3, Kelly3_optimized, Seon_optimized

# Correctness
for n in *range(10001), 65536:
    expect = str(funcs[0](n))
    for f in funcs[1:]:
        result = str(f(n))
        assert result == expect

# Speed
times = {f: [] for f in funcs}
def stats(f):
    ts = [t * 1e6 for t in sorted(times[f])[:100]]
    return f'{mean(ts):6.2f} ± {stdev(ts):4.2f} μs '
for _ in range(1000):
    for f in funcs:
        t = timeit(lambda: f(65536), number=1)
        times[f].append(t)
for f in sorted(funcs, key=stats):
    print(stats(f), f.__name__)

- Kelly Bundy