11. Factorial

Factorial

    这个题目已经做过N多遍了，在各大OJ上都有。
     题目大意：给定一个正整数n,求n!未尾有多少个0。
     算法分析：我们很容易发现阶乘未尾的0是由5产生的，即n!中有多少个5就有多少个0。从而问题就转化为求n!中分解质因数后5的系数。我们对其进行分类计数，首先求是5的倍数的数多少个，然后再求25的倍数，再求125的倍数，…………，直到为0。最后把这些数全部加起来即为答案。为什么可以这样呢？比如求25的倍数时5不是每一个都出现了两次却只计数一次吗？非也！我们在求5的倍数时已经给25的倍数计数过一次，同理求5的倍数和求25的倍数时也给125的倍数计数过一次…………。这种方法可以用在对n!进行质因数分解中，首先求1~n之间的素数，然后对每一个素数按照上面的方法求系数即可！
    

#include <iostream>
#include <cstdio>//注意此题的输入输出最好用scanf,printf，因为数据量比较大
using namespace std;
int getZero(int n)
{
    int sum=0;
    while(n)
    {
        sum+=n/5;
        n/=5;
    }
    return sum;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        printf("%d\n",getZero(n));
    }
    return 0;
}