求N！尾数有多少个0。

方法一：假设N！=K*10，K不能被10整除，那么N！尾数就有M个0。再对N！进行质因子分解：N！=2*3*5...由于10=2*5，即每一对2和5相乘都可以得到1个0，所以M只与指数x、z有关，并且M=min(x,z)（x，z分别为N！的中因子2，因子5的个数）。因为N！中每两个数字就有一个数为2的倍数，即每5个数中（最后一个数为5的倍数）至少有2个数为2的倍数，而只有最后一个数为5的倍数，所以可知因子为2的个数一定不小于因子为5的个数（x>=z），即M=z。因此，我们只需统计N！中因子为5的个数即可！时间复杂度为O(nlogn)，其中n=N/5。

 #include<bits/stdc++.h>

 using namespace std;

 int main(){

     int n,cnt,tmp;

     while(cin>>n){

         cnt=;

         for(int i=;i<=n;i+=){//n!内i只有为5的倍数才可产生因子5

             tmp=i;

             while(tmp%==)cnt++,tmp/=;//累加因子5的个数

         }

         cout<<cnt<<endl;

     }

     return ;

 }

方法二：如果N是10呢，用方法一肯定会超时。此时有一条公式可以快速地求出N！尾数为0的个数：M=[N/5]+[N/5]+[N/5]+...公式的意思就是不大于N且为5的倍数的每个数各贡献一个因子5加上不大于N且为5的倍数的每个数各贡献一个因子5加上...，将所有结果累加即为N！中因子5的个数。时间复杂度为O(logN)。举个例子：当N=25时，N！内为5的倍数的数有5，10，15，20，25，对应数字包含因子为5的个数为1，1，1，1，2，（很明显通过法一可知25！尾数有6个0）套一下法二的公式：N内为5的倍数的个数有N/5=25/5=5个，即前面5个数各贡献一个因子5，继续累加：N/5=25/25=1个，即最后一个数25也贡献一个因子5，所以25！尾数有6个0，因此验证了法二的正确性。其实这里用到了一个数论知识：若p是质数，p<=n，则N！是p的倍数，设p为p在N！内的最高次幂，则x=[N/p]+[N/p]+[N/p]+...，并且有[N/(p*p)]=[[N/p]/p]。结合法一可知p=5，即只需求N！内因子为5的个数！

 #include<bits/stdc++.h>

 using namespace std;

 int main(){

     int n,cnt;

     while(cin>>n){

         cnt=;

         while(n>4)cnt+=n/,n/=;

         cout<<cnt<<endl;

     }

     return ;

 }