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

a327904410

题目要求算出结果末尾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

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

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

kogawananari

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

jhq999

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

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

把所有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

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

可以，学到了。