Python高效计算阶乘最右侧非零数字的算法需求

原代码直接计算完整阶乘再处理的方式，在n=65536时会生成一个极其庞大的整数，无论是计算、存储还是字符串处理都会严重超时。我们需要换一种不需要生成完整阶乘的思路。

核心思路 #

阶乘末尾的0全部来自于因子2和5的乘积，所以我们可以：

• 先统计阶乘中2和5的总因子数，去掉等量的2和5（每对产生一个0）
• 对剩下的所有数（去掉2和5因子后的数）进行相乘，过程中只保留末尾几位非零数字（避免数值过大）
• 最后补上多余的2的乘积，再取最后一位非零数字

代码实现 #

def last_non_zero_digit(n):
    count2 = 0
    count5 = 0
    result = 1
    
    # 统计2和5的因子数，同时计算去掉2、5后的乘积
    for i in range(1, n+1):
        num = i
        # 剥离当前数中的所有2因子并计数
        while num % 2 == 0:
            count2 += 1
            num //= 2
        # 剥离当前数中的所有5因子并计数
        while num % 5 == 0:
            count5 += 1
            num //= 5
        # 累积乘积，取模100000保留足够位数，防止丢失有效信息
        result = (result * num) % 100000
    
    # 计算多余的2的数量（2的因子数一定比5多）
    extra_2 = count2 - count5
    # 补上多余的2的乘积
    result = (result * (2 ** extra_2)) % 100000
    
    # 去掉末尾残留的0，取最后一位
    while result % 10 == 0:
        result //= 10
    return result % 10

n = int(input())
print(last_non_zero_digit(n))

代码说明 #

• 遍历1到n的每个数，逐个剥离其中的2和5因子，同时统计总数，彻底分离所有会产生0的因子。
• 每次将剥离后的数乘到结果里，取模100000是因为我们只需要最后几位有效数字，保留5位足够避免中间计算丢失关键信息，同时保持数值不会过大。
• 因为2的因子数必然多于5，最后补上多余的2的幂次，再取模。
• 最后去掉末尾可能残留的0，取最后一位就是最终答案。

这个方法的时间复杂度为O(n log n)，对于n=65536来说完全可以在0.5秒内完成计算，且内存占用极低，不会出现大整数处理的性能问题。

内容的提问来源于stack exchange，提问作者Shayan