n！末尾0的个数

小鱼儿 2022-05-27 07:13 190阅读 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