[已解决]关于阶乘运行时间优化问题

a327904410 · 发表于 2021-10-10 17:04:50

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

题目要求算出结果末尾0的个数（因为它也知道数值很大），下面是我的代码，运行时间超时

。
举个例子：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;
}

复制代码

最佳答案

月排行榜 / 总排行榜

jhq999

2021-10-10 19:34:19

本帖最后由 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;

复制代码

跳转到最佳答案楼层

a327904410 · 发表于 2021-10-10 17:05:38

面对巨大数值的运算而导致运行超时的，一般怎么解决这类问题

kogawananari · 发表于 2021-10-10 17:08:42

只需要求0的个数何必求阶乘

jhq999 · 发表于 2021-10-10 18:03:49

提供个思路
只有两种情况：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 19:34:19

这个最佳答案由 jhq999 给出，感谢 jhq999 的回答。

单击隐藏图章

本帖最后由 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 19:39:44

本帖最后由 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

a327904410 · 发表于 2021-10-11 21:38:42

jhq999 发表于 2021-10-10 19:39
把所有5的倍数分解成里面有多少5，
例：125=5×5×5；75=5×5×3；
3个加上2个5=5个5，以此类推999999998 ...

可以，学到了。

账号		自动登录	找回密码
密码			立即注册

[已解决]关于阶乘运行时间优化问题

马上注册，结交更多好友，享用更多功能^_^

浏览过的版块