n！末尾0的个数

小鱼儿 2022-05-27 07:13 161阅读 0赞

**肯定不能直接求出 n! 然后在计算后边有多少个0**

**因为 1000000! 的位数就是 5565709**

**对于 n！ 的末尾如果有一个 0 的话，必然有一个 5 与其对应着**

**所以就是找从 1 到 n 这些数的约数（因子）中有多少个 5**

**它们有几个 5, n! 末尾就有几个0**

**令f(x)表示正整数x末尾所含有的“0”的个数，则有：**

**f(n!) =\[n/5\]+\[n/25\]+\[n/125\]+\[n/625\]+......**

**\[\] 表示向下取整**

**显然：**

**当0 < n < 5时，f(n!) = 0;  
 当n >= 5时，f(n!) = k + f(k!), 其中 k = n / 5（取整）。**

第一种，递归的形式

#include<cstdio>
    int cal(int n)
    {
    	if(n<5)	return 0;
    	n=n/5;
    	return n+cal(n);
    }
    int main()
    {
    	int t,n;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d",&n);
    		printf("%d\n",cal(n));
    	}
    	return 0;
    }

第二种，用循环来解决

#include<cmath>
    #include<cstdio>
    int main()
    {
    	int t,n;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d",&n);
    		int sum=0,c=5;
    		while(n/c!=0)
    		{
    			sum+=n/c;
    			c*=5;
    		}
    		printf("%d\n",sum);		
    	}
    	return 0;
    }

也可以这样写：

#include<cstdio>
    int main()
    {
    	int t,n;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d",&n);
    		int sum=0;
    		while(n)	sum+=(n/=5);
    		printf("%d\n",sum);	
    	}
    	return 0;
    }

参考:[https://blog.csdn.net/qq\_16255321/article/details/37994015][https_blog.csdn.net_qq_16255321_article_details_37994015]

题目练习:[HDU1124][]

[https_blog.csdn.net_qq_16255321_article_details_37994015]: https://blog.csdn.net/qq_16255321/article/details/37994015
[HDU1124]: http://acm.hdu.edu.cn/showproblem.php?pid=1124

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

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

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

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

相关 N个数求和

\include<stdio.h> long long gcd\_gcd(long long x,long long y) //求最大公约数 \{ int x

爱被打了一巴掌/ 2022年07月12日 10:42/ 0 赞/ 164 阅读

相关 n！末尾0的个数

肯定不能直接求出 n! 然后在计算后边有多少个0 因为 1000000! 的位数就是 5565709 对于 n！的末尾如果有一个 0 的话，必然有一个 5 与其

小鱼儿/ 2022年05月27日 07:13/ 0 赞/ 162 阅读

相关 n!的末尾0的个数

题目描述： > 输入一个正整数n,求n!(即阶乘)末尾有多少个0？比如: n = 10; n! = 3628800,所以答案为2 。解题思路： > 对于这样的问题，我

喜欢ヅ旅行/ 2022年05月18日 04:50/ 0 赞/ 164 阅读

相关一个阶乘中末尾零的个数

//给定一个正整数n，请计算n的阶乘n！末尾所含有“0”的个数。 5！=120，其末尾所含有的“0”的个数为1； 10！= 3628800，其末尾所含有的“

分手后的思念是犯贱/ 2022年01月05日 23:19/ 0 赞/ 242 阅读

相关笔试算法题（33）：烙饼排序问题 & N！阶乘十进制末尾0的个数二进制最低1的位置...

出题：不同大小烙饼的排序问题：对于N块大小不一的烙饼，上下累在一起，由于一只手托着所有的饼，所以仅有一只手可以翻转饼（假设手足够大可以翻转任意块数的饼），规定所有的大饼都出现

梦里梦外;/ 2021年12月23日 01:51/ 0 赞/ 171 阅读

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