力扣 172. 阶乘后的零_n的阶乘后0的个数力扣-CSDN博客

本文解析如何通过统计[1,n]中5的因子个数来确定阶乘中尾部0的个数，关键在于递归地减小n并累计因子5的贡献。算法核心在于不断除以5直到n不足5。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目来源：https://leetcode-cn.com/problems/factorial-trailing-zeroes/

大致题意：
给一个整数 n，求出 n 的阶乘中尾部 0 的个数

思路

尾部的 0，即为阶层乘积中因子 10 的个数，而 10 = 2 * 5，于是 0 的个数即为阶乘乘积因子中 2 和 5 之间的最小值

而 5 因子个数一定小于 2 因子的个数，所以这道题可以变成求 5 因子的个数

于是可以通过求 [1,n] 中因子 5 的个数得到答案

[1,n] 中因子 5 的倍数有 n / 5 个，这些数贡献了 n / 5 个因子 5
[1,n] 中因子 5² 的倍数有 n / 5² 个，这些数相比较之前额外贡献了 n / 5² 个因子 5
…
[1,n] 中因子 5ⁱ 的倍数有 n / 5ⁱ 个，这些数相比较之前额外贡献了 n / 5ⁱ 个因子 5

这样递归下去，直至 5ⁱ 大于 n，过程中即可统计出[1,n] 中因子 5 的个数

具体实现时，可以每次统计后将 n 的值除以 5，而不用更改除数的值

public int trailingZeroes(int n) {
        int ans = 0;
        while (n >= 5) {
            n /= 5;
            ans += n;
        }
        return ans;
    }