关于阶乘运行时间优化问题
题目要求算出结果末尾0的个数（因为它也知道数值很大），下面是我的代码，运行时间超时{:10_297:} 。举个例子：999999998的阶乘末尾有多少个0答案是249999989
#include<stdio.h>
int main() {
long long int a, sum = 1;
scanf("%lld", &a);
while (a > 0) { // 阶乘
sum *= a;
a--;
}
int i;
for (i = 0;; i++) { // 计算末尾0个数
if (sum % 10 == 0) { // 检查末尾是否存在0
sum /= 5;
}
else
break;
}
printf("%d", i);
return 0;
}
面对巨大数值的运算而导致运行超时的，一般怎么解决这类问题 只需要求0的个数何必求阶乘 提供个思路
只有两种情况：5的奇数倍和偶数相乘后积后面带0，而5的偶数倍自己带0。
2×5=10；
10；
4×15=60；
20
6×25=150；
30
8×35=280；
40
12×45=540
45！就是9个零
50
14×55=？？
……
本帖最后由 jhq999 于 2021-10-10 20:34 编辑
int i=0,len5=0,len2=0，tmp=0,num=999999998;
i=2;
while(i<=num)
{
if(0==i%2)
{
tmp=i;
while(tmp>0&&!(tmp%2))
{
len2++;
tmp/=2;
}
}
i+=2;
}
i=5;
while(i<=num)
{
if(0==i%5)
{
tmp=i;
while(tmp>0&&!(tmp%5))
{
len5++;
tmp/=5;
}
}
i+=5;
}
printf("%d",len2<len5?len2:len5);
return 0; 本帖最后由 jhq999 于 2021-10-10 20:20 编辑
把所有5的倍数分解成里面有多少5，
例：125=5×5×5；75=5×5×3；
3个加上2个5=5个5，以此类推999999998！可以分解到249999989个5；
又可以分解到799999999个不是5的倍数个2，够5乘的，所有相乘挂0的数的都多少个2×5=10
125×8=1000，5×5×5×2×2×2=1000
10！=10×9×8×7×6×5×4×3×2×1=2×5×9×7×……×5×……×1；
2个5，8个2 所以结果后面挂2个0 jhq999 发表于 2021-10-10 19:39
把所有5的倍数分解成里面有多少5，
例：125=5×5×5；75=5×5×3；
3个加上2个5=5个5，以此类推999999998 ...
可以，学到了。{:10_256:}
页:
[1]