（ACM数论）求N的阶乘末尾有多少个0

港控/mmm° 2022-07-17 03:23 171阅读 0赞

问题描述：给定一个整数N，那么N的阶乘N！末尾有多少个0？

这个问题的难点在于，不能直接计算出N！，因为会溢出。

既然不能直接计算，那就换个姿势计算（手动滑稽）

首先，我们考虑到N！末尾0的个数和 N！有多少个因子10有关，而10 = 2 \* 5 ，于是我们得到了一个解法：

把2，3，… ,N每个数拥有因子2的个数累加起来记为countTwo，把2，3，… ,N每个数拥有因子5的个数累加起来记为countFive，问题的答案则为min(countTwo, countFive)

代码如下：

int countTwo = 0, countFive = 0;
    for(int i = 2 ; i <= N ; i++)
    {
        int tmp = i;//每个数
        while(tmp % 2 == 0)
        {
            tmp = tmp / 2;
            countTwo++;
        }
        while(tmp % 5 == 0)
        {
            tmp = tmp / 5;
            countFive++;
        }
    }
    //min(countTwo, countFive)
    printf("ans = %d\n", 
    countFive < countTwo ? countFive :countTwo);

输入不同的N可以发现，countFive 必然小于 countTwo，这是由于：5^n > 2^n，即每有一个因子5，就必定会有一个因子2。  
所以解法可以改为把2，3，… ,N每个数拥有因子5的个数累加起来记为countFive，问题答案为countFive，代码如下：

int countFive = 0;
    for(int i = 5 ; i <= N ; i++)
    {
        int tmp = i;//每个数
        while(tmp % 5 == 0)
        {
            tmp = tmp / 5;
            countFive++;
        }
    }
    printf("ans = %d\n", countFive);

发表评论取消回复

表情：

评论列表（有 0 条评论，171人围观）

还没有评论，来说两句吧...

相关阅读

相关面试题：计算 n！阶乘的结果的末尾有几个0

前言首先基于一个事实：我们不可能真的把 n! 的结果计算出来，再去数结果的末尾有几个0；n 很小还好，如果n很大，甚至趋近于无穷大，我们是不可能这样做的。原因主要有...

梦里梦外;/ 2024年04月17日 06:30/ 0 赞/ 29 阅读

相关数学——技巧——判断阶乘尾部有多少个0

于n的阶乘，末尾有多少个0 一、朴素做法：朴素做法就是求出n！。然后每次对10去摸，再除以10。就比如5 5！ = 120； ...

秒速五厘米/ 2024年04月17日 05:58/ 0 赞/ 33 阅读

相关 java求n的阶乘

一个正整数的阶乘（factorial）是所有小于及等于该数的[正整数][Link 1]的[积][Link 2]，并且0的阶乘为1 亦即n!=1×2×3×...×n。阶乘亦可以

短命女/ 2024年02月19日 12:27/ 0 赞/ 56 阅读

相关 C\C++求N的阶乘！的值中末尾0的个数实践小记

C\\C++求N的阶乘！的值中末尾0的个数实践小记一、问题描述二、问题解决思路三、实践源码方法一：测试数据1

秒速五厘米/ 2022年12月28日 07:26/ 0 赞/ 106 阅读

相关求N!中末尾有多少个0

http://blog.csdn.net/cow\_\_sky/article/details/36190587 分析：对N进行质因数分解 N=2^x \ 3^y \ 5

逃离我推掉我的手/ 2022年09月26日 02:49/ 0 赞/ 148 阅读

相关求n的阶乘末尾有几个零

通过因数分解知道，10是由2和5相乘得到的，而在n的阶乘中，因子2的数目总是比5多的，所以最终末尾有几个零取决于其中有几个5。1到n中能够整除5的数中有一个5，能整除

布满荆棘的人生/ 2022年08月22日 13:28/ 0 赞/ 156 阅读

相关【编程之美】给定一个整数N，求N!末尾有多少个0

问题：给定一个整数N，求N!末尾有多少个0 这个题目不能直接求出N!的值，这样可能会溢出。首先考虑N!=K\10^M,并且K不能被10整除，那么N!末尾有M个0。再考虑对N

「爱情、让人受尽委屈。」/ 2022年08月04日 17:58/ 0 赞/ 144 阅读

相关（ACM数论）求N的阶乘末尾有多少个0

问题描述：给定一个整数N，那么N的阶乘N！末尾有多少个0？这个问题的难点在于，不能直接计算出N！，因为会溢出。既然不能直接计算，那就换个姿势计算（手动滑稽）首先，我

港控/mmm°/ 2022年07月17日 03:23/ 0 赞/ 172 阅读

相关小朋友学数学（23）：求2000！末尾有多少个0

一、思路一个数末尾的0是由2和5乘出来的，而1到2000里2多得是，主要看1到2000中有多少个5或5的n次方的倍数。（1）统计5的倍数 2000/5=400

青旅半醒/ 2022年03月20日 04:26/ 0 赞/ 457 阅读

相关阶乘N!的末尾有多少个0

思路：5\2=10,即每个5与2都能产生一个0，而在阶乘中，偶数很多，即2比5多 1-N中有N/5个数，每个数能贡献一个5,1-N有N/5^2个数，每个数又能贡献一个5等等

川长思鸟来/ 2021年09月26日 14:48/ 0 赞/ 348 阅读