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

秒速五厘米 2024-04-17 05:58 58阅读 0赞

对于n的阶乘， 末尾有多少个0

##### 一、朴素做法： #####

朴素做法就是求出n！。然后每次对10去摸， 再除以10。

就比如5
    5！ = 120；
    
    fac = 5!
    ans = 0;
    while（1）
    {
    	if(fac%10 == 0)ans++;
    	else break;
    	fac/=10;
    }

这种做法的弊端是， n不能太大， n太大 n的阶乘无法储存。

##### 二、 #####

想一下n！阶乘末尾的0取决于什么？

对于每个结尾的 0 都是10 导致的， 对10进行质因子分解2\*5。

这里先举个栗子。
    比如5的阶乘 == 120。 
    就可以看成12 *10 —— 12*5*2

所以只要统计 （1～n）中因子2和因子5的个数。  
然后再取小， 就是 n的阶乘末尾0的个数。

因为（1～n）内因子2个数肯定大于 因子5个数。

所以问题就转换为（1～n）内因子5的个数。

##### 如何求（1～n）因子5的个数。 #####

要知道因子5一定来自与它的倍数。

所以首先要知道n内5的倍数有多少个，  
n内5的倍数数量 == n/5， 这里是整除。

**就比如n == 30：**

1、 2、 3、 4、 5、 6 、…30  
（5的倍数 30/5个）

> 5 、10、 15、 20、 25、 30

这个数列可以提取因子5 后， 可以表示为：

> 5\*\[1、2、 3、 4、 5、 6\] 这是找到了 6个因子5

对于 内部 1 、 2 、3、 4 、5 、6 这个又可一看成n==6 时， 地归寻找。  
[推荐——>][Link 1]

求n！阶乘末尾有几个0
    long long found(long long n)
    { 
    	long long  ans = 0;
    	while(n)
    	{ 
    		ans+=n/5;//求 n内 5的倍数个数
    		n/=5;  // 提取因子5的操作。
    	}
    	return ans;
    }

相关题目：  
https://vjudge.net/problem/POJ-1426

[Link 1]: https://blog.csdn.net/surp2011/article/details/51168272

发表评论取消回复

表情：

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

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

相关阅读

相关 java判断开头有几个0_如何判断1024！末尾有多少个0

分析：方法一：暴力法简单的方法就是就算出1024！的值，然后判断末尾有多少个0.但是这种方法有两个非常大的缺点：第一算法效率非常低下；第二：当这个数字比较大的时候直接计

以你之姓@/ 2022年11月07日 15:58/ 0 赞/ 185 阅读

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

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

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

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

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

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

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

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

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

相关 172. Factorial Trailing Zeroes （计算n的阶乘尾部有多少个零）

Given an integer n, return the number of trailing zeroes in n!. Note: Your solution sho

r囧r小猫/ 2022年07月15日 01:21/ 0 赞/ 168 阅读

相关 172. Factorial Trailing Zeroes （计算n的阶乘尾部有多少个零）

Given an integer n, return the number of trailing zeroes in n!. Note: Your solution sho

红太狼/ 2022年07月15日 01:21/ 0 赞/ 166 阅读

相关计算n阶乘中尾部零的个数

今天开始算法练习，刚开始感觉挺简单的一个题，怎么就让自己乱了手脚。题目：设计一个算法，计算n阶乘中尾部零的个数结果： 11! = 39916800，因此应该

ゝ一世哀愁。/ 2022年06月01日 09:36/ 0 赞/ 209 阅读

相关尾部的零（设计一个算法，计算出n阶乘中尾部零的个数）

这里我们知道，大家最平常的思维就是用一个数来接收n阶乘后的数，然后再来判断那个和的尾部的0的个数，这样的算法算得上O（n）级，还有一个隐患，就是就算用long来存储数据，也不会

桃扇骨/ 2022年05月19日 07:21/ 0 赞/ 173 阅读

相关小朋友学数学（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 赞/ 490 阅读

相关阶乘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 赞/ 441 阅读