阶乘的0
时间限制：3000 ms | 内存限制：65535 KB
难度：3
描述
计算n!的十进制表示最后有多少个0
输入
第一行输入一个整数N表示测试数据的组数(1<=N<=100)
每组测试数据占一行，都只有一个整数M(0<=M<=10000000)
输出
输出M的阶乘的十进制表示中最后0的个数
比如5!=120则最后的0的个数为1
样例输入
6
3
60
100
1024
23456
8735373样例输出
0
14
24
253
5861
2183837解题思路：因为在质数中，只有2和5相乘才会在尾部出现一个"0"，那么只要将m分解质因数，然后统计2和5的个数，其中较小的一个就是答案。
进一步来说，m分解质因数之后，2的个数绝对比5多，那么问题进一步简化，只要统计出所有的质因数中有多少个5即可。
例如：
5!=5*4*3*2*1=120,其中有1个5、1个2，所以最后有1个0
10!=10*9*8*7*6*5*4*3*2*1=3628800,连乘积可以写成(5*2)*(3*3)*(2*2*2)*7*(3*2)*5*(2*2)*3*2*1，其中有2个5、8个2，因子5的个数即为最后0的个数，所以最后有两个0
用比较笨的方法算一下:
1—>3000里面5的倍数有：
5,10,15,25,……95,100,105,110,115,125,……195,200,……2995,3000
那么5的个数是3000÷5＝600(个)
而其中只要是5^2=25的倍数的数就能分解成2个5,例如：
25,50,75,100,125,150,175,200,225,……3000,这些数要算2个5,所以5的个数就要多加1次这些数的个数,
那么在上面这堆数里面25的个数是3000÷25＝120(个)
而其中只要是5^3=125的倍数的数就能分解成3个5,例如：
125,250,375,……3000,这些数要算3个5,所以5的个数就又要多加1次这些数的个数
那么在上面这堆数里面125的个数是3000÷125＝24(个)
而其中只要是5^4=625的倍数的数就能分解成4个5,例如：
625,1250,1875,2500,这4个数要算4个5,所以5的个数就又要多加1次这些数的个数
那么在上面这堆数里面125的个数是3000÷625＝4.8,这里实际就是只能有4个625的倍数了
所以5的个数实际是600+120+24+4＝748(个)
[cpp]
#include
int main()
{
int t,sum,n;
scanf("%d",&t);
while(t--)
{
sum=0;
scanf("%d",&n);
while(n)
{
n/=5;/*分解质因数，统计5的个数*/
sum+=n;
}
printf("%d\n",sum);
}
return 0;
}
#include
int main()
{
int t,sum,n;
scanf("%d",&t);
while(t--)
{
sum=0;
scanf("%d",&n);
while(n)
{
n/=5;/*分解质因数，统计5的个数*/
sum+=n;
}
printf("%d\n",sum);
}
return 0;
}