计算n的阶乘有多少个尾随零

思路一：

计算出n！= nValue，然后 nValue % 10 == 0 则nCount自增1，nValue /= 10 直到条件为否，最后nCount就是我们想要的结果，代码如下：

 int CountZero(int n)

 {

     unsign long long nValue = ;

     for (int i = ; i <= n; i ++)

     {

         nValue *=i;

     }

     int nCount = ;

     while( == nValue % )

     {

         nCount ++;

         nValue /= ;

     }

     return nCount;

 }

代码简洁易懂，看上去还不赖，但是这里要考虑一个问题就是在求n！整数溢出了怎么办？显然我们使用_int64也同样会有溢出的时候，所以上面的代码实际上是不可行的。

思路二：

不知道怎么办，不妨先举例分析：

！ =

！ =  *  =

！ =  *  * =

！ =  *  *  *  =

！ =  *  *  *  *  =

........

 *  *  *  *  *  *  *  *  *  *  *  *

*  *  *  *  *  *  *  *  *  * *  *

我们会发现一个因子2和因子5组合产生一个0，这样我们只需统计1到n有多少个因子对，即n！的尾随零个数，因子2的个数比因子5的个数多，因此我们只需统计出因子5的个数即可，如

,,,,,,.......

需要注意的是，以100！为例：

统计一次5的倍数（5,10,15,20,25,30,35,40,45,50,55,60,65,70,75,80,85,90,95,100）= 20

统计一次25的倍数（因为25的倍数有两个5的因子，所以再统计一次）（25,50,75,100） = 4

统计一次125的倍数（125的倍数由3个5的因子，所以再统计一次，以此类推）（nil）

所以100！的尾随零个数为24个

实现代码如下：

 int CountZero(int n)

 {

     int count = ;

     if (n < )

         return -;

     for (int i = ; n / i > ; i *= )

         count += n / i;

     return count;

 }

运行结果：

当n=21时，21！已经溢出。

巴特西

计算n的阶乘有多少个尾随零

最新文章

热门文章