本文通过数学分析给出了输出n!末尾0的个数之函数的递归形式，并同时给出了两种本问题的枚举解法。

问题描述

给定正整数n, 计算n!末尾0的个数。例：

5! = 120, 故 5! 结尾0的个数为1.
10! = 3628800, 故 10! 结尾0的个数为2.
25! = 15511210043330985984000000, 故 25! 结尾0的个数为6.

分析

导致末尾0出现的原因

众所周知，当一个正整数n与10相乘时会产生进位，即10n的末尾会比n多1个0。类似地，当一个正整数n与$10^{k}$相乘时，所得结果的末尾会比n多k个0. 又，由算术基本定理：

每个大于1的自然数均可写为质数的积，而且这些素因子按大小排列之后，写法仅有一种方式。

可知欲计算n!末尾0的个数，只需查找其分解中10的个数，也即查找n!的素因子分解中相乘等于10的两个质数组合的个数。

命题1：10的素因子分解是2 * 5.

证明：因为10是合数，所以10可记作多个质数之积。又因为10是偶数，所以10的素因子分解不能全为奇数。而偶素数只有2，故10的素因子分解中必有2，又10 / 2 = 5, 故10的素因子分解为2 * 5. 证毕。

由此可见，欲计算n!末尾0的个数，只需统计n!的素因子分解中因子(2 * 5)的个数。又，因为奇数与偶数交替出现，所以每2个连续数字就会出现一个因子2，而每5个连续数字才会出现一个因子5，故因子(2 * 5)的个数即因子5的个数。此时，原问题转化为：计算n!的素因子分解中5的个数。

计算n!的素因子分解中5的个数

为了计算正整数n的素因子分解中5的个数，我们可以计算n的某个分解中5的倍数的个数。

由除法定理，任一正整数$n$可记作$n=5k+r$, 其中$k=\left \lfloor \frac{n}{5} \right \rfloor$, $0\leq r\leq 4$。则$n!$的一个分解为$$n!=5k \cdot 5(k - 1) \cdot 5(k - 2) \cdots 5 \cdot A $$,即$$ n!=5^{k} \cdot k! \cdot A$$,其中$A$为不含因子5的因子。

此时定义函数$f(n)$输出正整数$n$末尾0的个数，$g(n)$输出正整数$n$素因子分解中因子5的个数。由前述易知$f(n) = g(n)$. 此时由g(n)的性质可导出以下命题：

命题2：$g(\prod_{i = 1}^{k} a_{i}) = \sum_{i = 1}^{k} g(a_{i})$, $a_{i}\in \mathbb{Z}$且$a_{i}\neq 0$.

证明：$\prod_{i = 1}^{k} a_{i}$的素因子分解为$a_{1}, a_{2}, \cdots, a_{u}, \cdots, a_{i}$的素因子分解之积，而后者中因子5出现的次数为数列$a_{i}$中每个元素之素因子分解中因子5出现的次数之和，故知前者的素因子分解中因子5的个数也等于上述和。证毕。

故知$f(n) = g(n) = g(5^{k} \cdot k! \cdot A) = k + g(k!) = k + f(k!)$, 其中$k = \left \lfloor n / 5 \right \rfloor$. 又易知$f(n!) = 0\ (0 \leq n \leq 4)$, 此时即获得$f(n!)$的递归关系，这就是所求问题的解。例：

f(5!) = 1 + f(1!) = 1
f(10!) = 2 + f(2!) = 2
f(25!) = 5 + f(5!) = 5 + 1 + f(1!) = 6

代码实现

int FactZero(int n){
    return n <= 4 ? 0 : (n / 5) + FactZero(n / 5);
}

枚举法

如果直接试图编程计算该问题，很容易导致溢出。但在进行了以上分析之后，即使未能得出最后的递归关系，只要知道求解本题只需统计n的素因子分解中5出现的次数，此问题亦可以用枚举法求解。

统计5的倍数(5，10，15，20，25(= 5 ^ 2))出现次数

int FactZero(int n){
    if(n <= 4)
        return 0;
    else{
        int i = 0, j = 0, count = 0;

        for(i = 5; i <= n; i += 5){
            j = i;
            while(j % 5 == 0){
                count++;
                j /= 5;
            }
        }
        return count;
    }
}

递归关系式的迭代形式

由上文分析的递归关系式，可知$$f(n!) = \left \lfloor n / 5 \right \rfloor + f(\left \lfloor n / 5 \right \rfloor!)$$$$=\left \lfloor n / 5 \right \rfloor + \left \lfloor n / 5^{2} \right \rfloor + f(\left \lfloor n / 5^{2} \right \rfloor!)$$$$=\left \lfloor n / 5 \right \rfloor + \left \lfloor n / 5^{2} \right \rfloor + \left \lfloor n / 5^{3} \right \rfloor + \cdots$$

故依次计算n / 5,直至n / 5 == 0输出结果。

int FactZero(int n){
    int count = 0;

    while(n > 0){
        count += n / 5;
        n /= 5;
    }
    return count;
}

n!末尾0的个数之计算