n!末尾有多少个0以及n!末尾第一个非0数字

只看该作者 · 2019-9-14 18:13

(1)n!末尾有多少个0

第一种思路:

n!=n*(n-1)*(n-2)*....3*2*1,而如果要出现0，必须得有2和5出现，但是明显n!中5的因子个数少于2的因子个数，即转化为求 n!中因子5的个数

int count(int n)

{　　

　　　　int sum=0;

while(n)

{

　　　　　　sum+=n/5;

n/=5;

}

return sum;

}

只看该作者 · 2019-9-14 18:16

第二种思路:计算n!，每次末尾出现0，则将0消去，计数器并自增1

   int count=0;

   int ans=1;

      for(i=n;i>=2;i--)
      {
         ans*=i;
         while(ans%10==0)       //消除末尾的0
         {
            ans/=10;

            count++;
         }
         if(ans>=100000)          //只需保存末尾5位数字即可
            ans%=100000;
      }

      while(ans%10==0)       //消除末尾的0
      {
            ans/=10;

            count++;
      }

      count即为所求

只看该作者 · 2019-9-14 18:16

(2)n!末尾第一个非0数字

两种思路

第一种:直接求出n!，然后得出结果

第二种:按照问题(1)中的第二种思路解决即可。

只看该作者 · 2019-9-14 18:16

作者：Matrix海子
　　　　
出处：http://www.cnblogs.com/dolphin0520/
　　　　
本博客中未标明转载的**归作者Matrix海子和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在**页面明显位置给出原文连接，否则保留追究法律责任的权利。

n!末尾有多少个0以及n!末尾第一个非0数字

相关下载

相关帖子