数学——技巧——判断阶乘尾部有多少个0

秒速五厘米 2024-04-17 05:58 266阅读 0赞

对于n的阶乘， 末尾有多少个0

一、朴素做法：

朴素做法就是求出n！。然后每次对10去摸， 再除以10。

  1. 就比如5
  2. 5！ = 120；
  4. fac = 5!
  5. ans = 0;
  6. while（1）
  7. {
  8.     if(fac%10 == 0)ans++;
  9.     else break;
  10.     fac/=10;
  11. }

这种做法的弊端是， n不能太大， n太大 n的阶乘无法储存。

二、

想一下n！阶乘末尾的0取决于什么？

对于每个结尾的 0 都是10 导致的， 对10进行质因子分解2*5。

  1. 这里先举个栗子。
  2. 比如5的阶乘 == 120。 
  3. 就可以看成12 *10 —— 12*5*2

所以只要统计 （1～n）中因子2和因子5的个数。
然后再取小， 就是 n的阶乘末尾0的个数。

因为（1～n）内因子2个数肯定大于 因子5个数。

所以问题就转换为（1～n）内因子5的个数。

如何求（1～n）因子5的个数。

要知道因子5一定来自与它的倍数。

所以首先要知道n内5的倍数有多少个，
n内5的倍数数量 == n/5， 这里是整除。

就比如n == 30：

1、 2、 3、 4、 5、 6 、…30
（5的倍数 30/5个）

5 、10、 15、 20、 25、 30

这个数列可以提取因子5 后， 可以表示为：

5*[1、2、 3、 4、 5、 6] 这是找到了 6个因子5

对于 内部 1 、 2 、3、 4 、5 、6 这个又可一看成n==6 时， 地归寻找。
推荐——>

  1. 求n！阶乘末尾有几个0
  2. long long found(long long n)
  3. { 
  4.     long long  ans = 0;
  5.     while(n)
  6.     { 
  7.         ans+=n/5;//求 n内 5的倍数个数
  8.         n/=5;  // 提取因子5的操作。
  9.     }
  10.     return ans;
  11. }

相关题目：
https://vjudge.net/problem/POJ-1426

发表评论

表情：
评论列表 （有 0 条评论，266人围观）

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

相关阅读