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

秒速五厘米 2024-04-17 05:58 94阅读 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 条评论，94人围观）

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

相关阅读

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

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

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

相关 0的阶乘是多少？0的算法，工龄有哪些计算法？

从0时到24时的计算法，通常叫做什么？从零时到24时的计算法通常叫做24点计算法。这是小学奥数里的经常算法之一。函数0比0型计算方法有哪几种？好吧我开玩笑的

你的名字/ 2023年09月28日 10:01/ 0 赞/ 15 阅读

相关输入一个正整数n,求n的阶乘末尾有多少个0

public class End0 { public static void main(String[] args) { Sca

灰太狼/ 2023年07月24日 09:14/ 0 赞/ 32 阅读

相关阶乘尾部0的个数

阶乘尾部0的个数输入输入数据有若干行，每行上有一个非负整数n，对应一种情形。输出对于每一种情形，直接输出结果、换行。样例输入 8 16

素颜马尾好姑娘i/ 2023年03月04日 06:54/ 0 赞/ 33 阅读

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

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

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

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

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

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

相关 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 赞/ 181 阅读

相关 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 赞/ 186 阅读

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

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