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