(笔试题)N!尾部连续0的个数

题目：

对任意输入的正整数N，编写C程序求N!的尾部连续0的个数，并指出计算复杂度。如：18！＝6402373705728000，尾部连续0的个数是3。 
（不用考虑数值超出计算机整数界限的问题）

思路：

1、直接计算N！的值，然后统计尾部0的个数，时间复杂度O(n)；

2、发散思维，想想尾部为0的数是怎么得到的？

很容易想到2*5即可得到0，则N!可以表示为k*（2^m）*（5^n），由于在N！中m>>n，因此N!=k'*(2*5)^n，即n为尾部为0的个数。

由此，我们只要考虑N!中包含多少个5的倍数就可以了，如25，含有5,10,15,20,25，包含6个5的倍数，即25！尾部有6个0。

n=N/5+N/(5^2)+N/(5^3)....+N/(5^k) (k<=N/5)

时间复杂度：O(logN)

代码：

#include <iostream>

using namespace std;

long long NumOfZero(long long n){

    long long count=0;

    while(n>0){

        count+=n/5;

        n=n/5;

    }

    return count;

}

long long factorial(long long n){

    if(n==1)

        return 1;

    return n*factorial(n-1);

    /*

    int fac=1;

    while(n>0){

        fac*=n;

        n--;

    }

    return fac;

    */

}

int main()

{

    long long n=20;

    cout<<NumOfZero(n)<<endl;

    cout<<factorial(n)<<endl;

    return 0;

}