题2：n阶乘尾部零的个数

题目描述：

设计一个算法，计算出n阶乘中尾部零的个数。注意：时间复杂度为O(lgn)。

思路：

要求n的阶乘，就是求1到n这n个数相乘。在这1到n个数当中，只有2和5相乘的结果才会出现0，其中10的倍数也可以看做是2和5相乘的结果，所以，可以在1到n之间看看有多少个数是2的倍数以及多少个数是5的倍数就行了。容易发现2的倍数的数一定多于5的倍数的数，因此可以只看n前面有多少个5就行了，于是n/5可以得到1到n内有多少个数是5的倍数。此外，还有一些特殊情况，比如25这种，其是5和5相乘的结果，这种数和4相乘会出现2个0，同理125和8相乘会出现3个0,……，所以，还要看n/5里面有多少个5，比如n=125，125个数里有25个数是5的倍数，125里又有125/25=5个数是25的倍数。每个25的倍数又会多一个0。因此125! 的末尾0的个数就是125/5 + 125/5/5 + 125/5/5/5。其中最后一项表示125的个数，因为125和8相乘会出现3个0。如果下面还有，比如625，即需要再循环一次，就是625的个数，625乘以16会出现4个0，需要再加1，依次类推……

代码：

#include<iostream>
using namespace std;

class Solution
{
public:
int TrailingZeros(int n)
    {
int sum = 0;
while(n)
        {
            n /= 5;
            sum += n;
        }
return sum;
    }
};

int main()
{
    Solution so;
cout<<"4的阶乘后有"<<so.TrailingZeros(4) <<"个0"<<endl;
cout<<"6的阶乘后有"<<so.TrailingZeros(6) <<"个0"<<endl;
cout<<"10的阶乘后有"<<so.TrailingZeros(10) <<"个0"<<endl;
cout<<"15的阶乘后有"<<so.TrailingZeros(15) <<"个0"<<endl;
cout<<"30的阶乘后有"<<so.TrailingZeros(30) <<"个0"<<endl;

    system("pause");
return 0;
}

拓展：

本题是求n! 的十进制形式的末尾 0 的个数（n /= 5），类似还有求2进制形式的末尾0的个数，3进制形式末尾0的个数。二进制就是 n /=2 ，三进制就是 n /= 3。