HDU1124 一个数的阶乘的结果中包含几个 0

╰+攻爆jí腚メ 2022-06-04 00:24 146阅读 0赞

## 分析： ##

输入整数 N，输出整数 N！ 中，十进制表示情况下， 末尾 0 的个数。  
因为 2\*5=10 。所以N! 表达式中，考虑 2,5 的公共次数 就可以。  
又因为 2的数目太多，所以公共次数 取决于 5的个数。  
所以问题就转化为 N! 表达式中，能够分解出来的 5 的个数。

### 方法一：直接进行简单的暴力进行求解 ###

#include <cstdio>   //G++  暴力简单模拟，超时。
    int main()
    {
        int value;
        int T;
        scanf("%d",&T);
        while(T--){
            scanf("%d",&value);
            if(value<=4)
                printf("0\n");
            else{
                int num = 0;
                int tmp = 1;
                for(int i=5;i<=value;i++){  //当 N=1e9 的时候，明显是 10秒啊，而且这才是一个案例。所以，不行。
                    if(i%5==0){
                        tmp = i;
                        while(tmp%5==0){
                            ++num;
                            tmp /= 5;
                        }
                    }
                }
                printf("%d\n",num);
            }
        }
        return 0;
    }

### 2.运用数学规律求解 ###

/*
    N!的乘法展开式中 ：是5的倍数的个数+是5^2的倍数的个数+5^3.....
    如50!：
    含有10个5的倍数的数：5,15,20,25,30,35,40,45,50 【50/5=10】
        含有2个5^2的倍数的数：25,50【50/(5^2)=2】
    可见N!中一共有12个5相乘，那么尾0也必有12个
    */

#include <cstdio>   //AC G++ 78ms
    int main()
    {
        int value;
        int T;
        scanf("%d",&T);
        while(T--){
            scanf("%d",&value);
            int num = 0;
            value /= 5;
            while(value > 0){
                num += value;
                value /= 5;
            }
            printf("%d\n",num);
        }
        return 0;
    }