题目地址：http://poj.org/problem?id=1401
我是从5的次幂数入手，看了网上的才发现原来可以那么简单.....
以下摘自其他博客
思路： 这一题要求的是N！中末尾0的个数，其实也就是所包含因子10的个数。10=5*2，因子10的个数也就是因子2的个数与因子5的个数中较小的那个，N！=1*2*3...*N，其中2的因子个数一定不少于5的因子个数，所以要求的其实就是N！中所包含的5的因子个数。
组合数学类型的题目。
正常的话可能会去分解1~N数里面有几个5和2，但是这样的复杂度为O(nlogn)。
其实有更巧妙的办法，可以把问题分解成子问题。
可以发现N!末尾的0与1~N中有几个5的因子相同(因为2总是比5多)。
1~N中只有5的倍数包含5因子，比如[5, 10, 15, 20...]，所以我们抽出其中每个数的一个5因子，这时候就只剩下[1, 2, 3, ...., N/5]了，其他没有5因子的就都给扔掉就行了。
你会发现新产生的这个序列又是一个相同的问题。
写出递推式就是：F(n) = n/5 + f(n/5)，可以用递归也可以用循环实现。
我的代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
int a[13],b[13],c[13];
int main(int argc, char const *argv[])
{int T; scanf("%d",&T);a[1]=5;REP(i,2,12) a[i]=a[i-1]*5; while(T--){int n; scanf("%d",&n);REP(i,1,12) b[i]=n/a[i];REP(i,2,12) c[i]=b[i]-b[i]/5;int ans=b[1]; REP(i,2,12) ans-=c[i]-c[i]*i;printf("%d\n",ans);}return 0;
}网上的代码：
#include <cstdio> int n, t; int main()
{ scanf("%d", &t); while (t--) { scanf("%d", &n); int ans = 0; while (n != 0) { ans += n / 5; n /= 5; } printf("%d\n", ans); } return 0;
}