如何高效计算前N个阶乘乘积的末尾零个数（N≤1e18）

核心推导 #

十进制末尾零的个数由乘积中因子2和5的最小计数决定，叠阶乘中因子2的数量远多于5，因此只需统计总因子5的个数即可。
叠阶乘的定义是1! * 2! * 3! * ... * n!，其总因子5的个数等价于所有i!中因子5个数的总和。
普通i!中因子5的个数为 floor(i/5) + floor(i/25) + floor(i/125) + ...，我们可以交换求和顺序，将总计数转换为：对每个5的幂次k=5^m，计算sum_{i=1}^n floor(i/k)，再把所有结果累加。

快速求和公式 #

对于sum_{i=1}^x floor(i/k)，有O(1)计算公式：

设 q = x // k，r = x % k，则求和结果为 q * (q - 1) * k // 2 + q * (r + 1)
5的幂次增长极快，到超过1e18最多仅需要26次迭代，整体复杂度为O(log n)，完全满足1e18量级的计算要求。

正确实现代码 #

def count_trailing_zeros(n):
    ans = 0
    k = 5
    while k <= n:
        q = n // k
        r = n % k
        ans += q * (q - 1) * k // 2 + q * (r + 1)
        k *= 5
    return ans

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