今天带来的是 SPOJ 第11题，计算N!末尾0的数目

这是该站上第二简单的题，共有5619人参与，19986个程序被提交，正确率为48.3%

原题

Input

There is a single positive integer T on the first line of input (equal to about 100000). It stands for the number of numbers to follow. Then there are T lines, each containing exactly one positive integer number N, 1 <= N <= 1000000000.

Output

For every number N, output a single line containing the single non-negative integer Z(N).

Example

Sample Input:

6
3
60
100
1024
23456
8735373

Sample Output:

0
14
24
253
5861
2183837

事实上这是一道广为流传的题目，当年本人在学校BBS上就有见过，据说还是微软的面试题。

不需要经过太多的思考就可以想到，一个数末尾0的个数取决于它的因子中10的数量，而10=2*5，因此分解质因数后因子2和5的个数决定了该数末尾0的个数，而显然前者必定不小于后者，因此本题实际上是计算N!中因子5的总数

以100为例，让我们手动推演一下这个过程，首先我们找出1-100中能被5整除的数，它们分别是5， 10， 15。。。。共[100/5]=20个，把这20个数除以5，以表示我们已完成的第一次筛选，这样得到1，2，3.。。20。重复刚才的过程，得到4个数1，2，3，4，无法再进一步分解。因此100！的阶乘中有20+4=24个质因子5。

观察上述过程可知，N！中质因子5的个数等于1-N中能分别被5，25，125.。。。5^k整除的数的总量，因此我们不需要遍历1到n的序列，只需要将n不断整除5，并加总各步的商，即是我们需要的结果。

以下是C的实现，

int main()
{
long num, fact, len, result;
scanf("%d", &len);
while (len--)
{
scanf("%d", &num);
result=0;
while (num/=5)
{
result+=num;
}
printf("%d\n", result);
}
return 0;
}

随机文章：

SPOJ 42-Adding Reversed Numbers(ADDREV) 2010-07-06支持python的online judge system 2010-05-23智力题做多了，智商就下降 2010-05-16每日一软 2009-07-15智能知识引擎wolfram|alpha 2009-05-30

色界频道——这里有顶尖的摄影大师，也有摄影爱好者，他们用相机收纳大千世界。

收藏到：Del.icio.us