求N！尾数有多少个0。

方法一：假设N！=K*10^M，K不能被10整除，那么N！尾数就有M个0。再对N！进行质因子分解：N！=2^x*3^y*5^z...由于10=2*5，即每一对2和5相乘都可以得到1个0，所以M只与指数x、z有关，并且M=min(x,z)（x，z分别为N！的中因子2，因子5的个数）。因为N！中每两个数字就有一个数为2的倍数，即每5个数中（最后一个数为5的倍数）至少有2个数为2的倍数，而只有最后一个数为5的倍数，所以可知因子为2的个数一定不小于因子为5的个数（x>=z），即M=z。因此，我们只需统计N！中因子为5的个数即可！时间复杂度为O(nlog₅n)，其中n=N/5。

 #include<bits/stdc++.h>

 using namespace std;

 int main(){

     int n,cnt,tmp;

     while(cin>>n){

         cnt=;

         for(int i=;i<=n;i+=){//n!内i只有为5的倍数才可产生因子5

             tmp=i;

             while(tmp%==)cnt++,tmp/=;//累加因子5的个数

         }

         cout<<cnt<<endl;

     }

     return ;

 }

方法二：如果N是10⁹呢，用方法一肯定会超时。此时有一条公式可以快速地求出N！尾数为0的个数：M=[N/5]+[N/5²]+[N/5³]+...公式的意思就是不大于N且为5的倍数的每个数各贡献一个因子5加上不大于N且为5²的倍数的每个数各贡献一个因子5加上...，将所有结果累加即为N！中因子5的个数。时间复杂度为O(log₅N)。举个例子：当N=25时，N！内为5的倍数的数有5，10，15，20，25，对应数字包含因子为5的个数为1，1，1，1，2，（很明显通过法一可知25！尾数有6个0）套一下法二的公式：N内为5的倍数的个数有N/5=25/5=5个，即前面5个数各贡献一个因子5，继续累加：N/5²=25/25=1个，即最后一个数25也贡献一个因子5，所以25！尾数有6个0，因此验证了法二的正确性。其实这里用到了一个数论知识：若p是质数，p<=n，则N！是p的倍数，设p^x为p在N！内的最高次幂，则x=[N/p]+[N/p²]+[N/p³]+...，并且有[N/(p*p)]=[[N/p]/p]。结合法一可知p=5，即只需求N！内因子为5的个数！

 #include<bits/stdc++.h>

 using namespace std;

 int main(){

     int n,cnt;

     while(cin>>n){

         cnt=;

         while(n>4)cnt+=n/,n/=;

         cout<<cnt<<endl;

     }

     return ;

 }

巴特西

求N！尾数有多少个0。

最新文章

热门文章