nyoj 84 阶乘的0

点击打开链接

阶乘的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

有两种方法,我想到的一种是从5开始一直循环到m,对于每个5的倍数都反复除以5,每次除5计数器加一(其实就是看m的阶乘能除多少次5)这个方法速度很慢接近1500MS,如果时间卡的严一点就TL了

#include<stdio.h>
int main()
{
int i , j , k , l;
int count;
scanf("%d" , & i);
while(i--)
{
count = 0;
scanf("%d" , &j);
for(k = 5 ; k <= j ; k += 5)
{
l = k ;
while(l % 5 == 0)
{
count++;
l /= 5;
}
}
printf("%d\n" , count);
}
return 0;
}

还有一种方法就是看m当中有的5^x(x从1开始递增直到5^x超过m)然后每次计数器加上x。这个方法时间是0ms

#include<stdio.h>
int main()
{
int i , j;
int num = 5 , sum , n;
scanf("%d" , &i);
while(i--)
{
scanf("%d" , &n);
for(num = 5 , sum = 0 ; n / num != 0 ;)
{
sum += n / num;
num *= 5; }
printf("%d\n" , sum);
}
return 0;
}
上一篇:【转】IE内嵌google chrome frame解决浏览器兼容问题


下一篇:docker下使用caffe的命令记录