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

wi3ka0sx  于 2023-06-04  发布在  Python
关注(0)|答案(3)|浏览(141)

高效计算n阶乘的最右非零位
我想计算一个给定数的阶乘的最右边的数字并打印出来。到目前为止我所做的是:

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

但我仍然有时间限制,我寻找更快的解决方案。值得注意的是,我必须使用python来解决这个问题。

**另外,我还要指出n是从1到65536,时间限制是0.5秒,我有256兆字节的内存。

tv6aics1

tv6aics11#

有一个简洁的递归公式可以用途:设D(n)是n中最后一个非零数字!

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

参见this math stackexchange post以获得证明。
把它翻译成代码:

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倍。

5kgi1eie

5kgi1eie2#

一个简单的足够快的方法,只需计算阶乘,然后删除与素数因子5出现的频率一样多的零(因为这是导致零的原因,以及更频繁的素数因子2)。从1到n的每五个数字贡献一个素数因子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

我们看到,只计算阶乘,而不提取所需的数字,是很容易足够快。只是你原来通过字符串提取数字的速度很慢。
(Note:OP 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!= 2twos * 5fives * ProductOfReducedFactors。由于2和5的配对会导致不需要的尾随零,因此请计算我们有多少个2不能与5配对。我的代码就是这么做的。则nFactorialWithoutTrailingZeros = 2 twos * ProductOfReducedFactors。我们用% 10得到它的最后一位,我们可以在整个计算过程中使用它来保持ProductOfReducedFactors较小。
测试代码(Attempt This Online!):

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__)
hc2pp10m

hc2pp10m3#

一个基于your answer的解决方案(只是重复你的还原步骤),一个击败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

代码(Attempt This Online!):

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

相关问题