昨天校赛有一道题,是求一个数的阶乘,末尾有几个零。当时是没有做出来的。今天网上看了下,明白了原理。其实很多人都写过了,自己之所以再写,一是为了加强自己的理解,二是有的地方或许可以写得更详细,也写出自己思考的一些误区。
回到题目本身,求一个数的阶乘,末尾有几个零 。
最容易想到的就是,(设这个数为n),求出n!,然后找出末尾有几个零。但,一旦n的值大了,就会溢出。
这里有一个更简单的解决办法。
求末尾几个零,最小的末尾带零的数就是10了。
10=2*5
每一对2,5就会产生一个0。
现在我们的问题就从求n!末尾有几个零,转为,n!有多少对2,5。
我们可以进一步将问题简化为,求n!拆分成的因子中有多少个5。为什么是5,不是2,是因为2出现的频率比5高。举个例子,200=2*5*2*5*2
给出计算公式
SUM=N/5+N/5/5+N/5/5/5+...[直到N为0截止] 公式1
N/5 指可以被5整除
N/5/5 指可以被25整除
N/5/5/5 指可以被125整除
SUM 指末尾0的个数
式子比较抽象,我们带入具体的值来理解下。
N=20,SUM=20/5=4,即末尾有4个0
不难理解,20!= 20*19*18*17*....*3*2*1
20,15,10,5 分别提供了一个5
有的同学可能看到这儿可能会这样想,每十个数,就有一对形如*5,*0的数,
那我们就可以得出这样一个公式
SUM=N/5 公式2
N=20,SUM=20/5=4
咋看起来是对,但这个是不全面了。
因为这个式子只考虑了被5整除的情况,没有考虑被5^2,5^3,5^4…整除的情况
为了方便理解,我们这儿同样取一个特殊的值,带入上述的两个公式来进行说明
N=25
带入公式1 SUM=N/5+N/5/5+N/5/5/5+...[直到N为0截止]
SUM=25/5+25/5/5=6
带入公式2 SUM=N/10*2
SUM=25/5=5
25!=25*24*23*...*3*2*1
取出形如*5,*0的数:25 20 15 10 5,共5个数
咦,5个数只会在末尾提供5个0呀
真的如此吗
25*24=600,这儿提供了两个0.
5*5*2*2*6=600
25是可以拆分成两个5相乘的,125是可以拆分成3个5相乘的,依次类推...
现在再回过头来看公式1
SUM=N/5+N/5/5+N/5/5/5+...[直到N为0截止] 公式1
N/5 指可以被5整除
N/5/5 指可以被25整除
N/5/5/5 指可以被125整除
SUM 指末尾0的个数
就容易理解公式了
这儿附上源码
#include<iostream>
using namespace std;
int main()
{
int m;
while(cin>>m)
{
int sum=0;
while(m){
sum+=m/5;
m=m/5;
}
cout<<sum<<endl;
}
return 0;
}