题目：
对任意输入的正整数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(log5N)
代码：
#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;
}
转播
