方法一：假設N！=K*10M，K不能被10整除，那麼N！尾數就有M個0。再對N！進行質因子分解：N！=2x*3y*5z...由于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(nlog5n)，其中n=N/5。
1 #include<bits/stdc++.h>
2 using namespace std;
3 int main(){
4 int n,cnt,tmp;
5 while(cin>>n){
6 cnt=0;
7 for(int i=5;i<=n;i+=5){//n!内i隻有為5的倍數才可産生因子5
8 tmp=i;
9 while(tmp%5==0)cnt++,tmp/=5;//累加因子5的個數
10 }
11 cout<<cnt<<endl;
12 }
13 return 0;
14 } 方法二：如果N是109呢，用方法一肯定會逾時。此時有一條公式可以快速地求出N！尾數為0的個數：M=[N/5]+[N/52]+[N/53]+...公式的意思就是不大于N且為5的倍數的每個數各貢獻一個因子5加上不大于N且為52的倍數的每個數各貢獻一個因子5加上...，将所有結果累加即為N！中因子5的個數。時間複雜度為O(log5N)。舉個例子：當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/52=25/25=1個，即最後一個數25也貢獻一個因子5，是以25！尾數有6個0，是以驗證了法二的正确性。其實這裡用到了一個數論知識：若p是質數，p<=n，則N！是p的倍數，設px為p在N！内的最高次幂，則x=[N/p]+[N/p2]+[N/p3]+...，并且有[N/(p*p)]=[[N/p]/p]。結合法一可知p=5，即隻需求N！内因子為5的個數！
1 #include<bits/stdc++.h>
2 using namespace std;
3 int main(){
4 int n,cnt;
5 while(cin>>n){
6 cnt=0;
7 while(n>4)cnt+=n/5,n/=5;
8 cout<<cnt<<endl;
9 }
10 return 0;
11 } 轉載于:https://www.cnblogs.com/acgoto/p/9465573.html