阶乘尾随零的数量

题目

阶乘尾随零的数量

信息

• 类型：问答
• 难度：⭐⭐

考点

数学分析,算法优化,边界条件处理

快速回答

计算阶乘结果中尾随零的数量，本质是统计因子5的个数。核心思路：

• 阶乘尾随零由因子2和5的对数决定
• 因子5的数量总是少于因子2的数量
• 只需计算5的因子个数：n/5 + n/25 + n/125 + ...
• 时间复杂度：O(log n)

原理说明

阶乘尾随零的数量取决于因子10的个数，而10由质因子2和5相乘得到。在阶乘中，因子2的数量总是多于因子5的数量（因为偶数更频繁）。因此问题转化为计算1到n中质因子5的总个数。

数学推导

统计因子5的个数需要分层计算：

• 第一层：能被5整除的数贡献1个5（共n/5个）
• 第二层：能被25整除的数额外贡献1个5（共n/25个）
• 第三层：能被125整除的数再贡献1个5（共n/125个）
• 以此类推直到除数大于n

代码示例

def trailing_zeroes(n: int) -> int:
    count = 0
    divisor = 5
    while divisor <= n:
        count += n // divisor
        divisor *= 5
    return count

# 测试案例
print(trailing_zeroes(25))  # 输出6 (25!有6个尾随零)
print(trailing_zeroes(10))  # 输出2

最佳实践

• 循环优化：使用divisor *= 5代替幂运算，避免浮点数精度问题
• 边界处理：n=0时返回0（0!定义为1，无尾随零）
• 复杂度控制：时间复杂度O(log₅n)，空间复杂度O(1)

常见错误

• 直接计算阶乘：n较大时（如n=1000）会导致整数溢出
• 忽略高阶因子：仅计算n//5会漏掉25、125等贡献的额外5因子
• 处理负数：题目通常限定n≥0，但实际编码可增加if n < 0: return 0

扩展知识

• Legendre公式：推广到任意质因子的计数方法，计算n!中质数p的幂次
• 变种问题：计算二进制阶乘尾随1的数量（统计因子2的个数）
• 数学证明：严格证明因子5数量≤因子2数量（floor(n/2) ≥ floor(n/5)）
• 实际应用：大数计算、密码学、组合数学中的精度控制