计算n!末尾所包含0的个数

转自：http://blog.csdn.net/waitfor_/article/details/7213288

 

 

例如，5！=120，其末尾所含有的“0”的个数为1；10！= 3628800，其末尾所含有的“0”的个数为2；20！= 2432902008176640000，其末尾所含有的“0”的个数为4。

这里先给出其计算公式，后面给出推导过程。令f(x)表示正整数x末尾所含有的“0”的个数，则有： 

      当0 < n < 5时，f(n!) = 0; 

      当n >= 5时，f(n!) = k + f(k!), 其中 k = n / 5（取整）。

从而可以递归求解。

证明：

           先证明一个结论。

           结论1： 对于n的阶乘n！，其因式分解中，如果存在一个因子“5”，那么它必然对应着n！末尾的一个“0”。

                         证明：首先我们知道在一堆乘法中产生0的途径只有2*5得到10，所以有几对2,5就可以得到几个0.下面我们可以将n！分解，n！= [5k * 5(k-1) * ... * 10 * 5] * a，其中 n = 5k + r (0 <= r <= 4)，a是一个不含因子“5”的整数。对于序列5,10,15，······，5(k-1),5k,中每一个数都含有因子5，并且在区间(5(k- 1),5k) 内总有一个2产生一个0，将上述序列提出一个5得到n！= 5^k * k! * a，其中k!可以递归的得到其满足结论1.

           有了上面的结论，我们知道f(n!) 只与5因子个数有关。f(n!) =  f(5^k * k! * a) = k + f(k!) = k + f(k!)，其中k = n / 5（取整）。