标签: 原理

……数零与进位

最近 AlphaGo 与李世石的人机围棋大赛很火,也蹦出一大波跳梁小丑。你会发现什么热点事件都少不了这种人,总是挡在路上,想不看都不行,比如那个输入法王。我记得上次 SoloLens 它也跳出来大谈 Matrix 来着。

牢骚完毕,这次深夜短篇不是写围棋也不是写计算机的,只说数数,更严格的说,只是数『0』。比如:

围棋棋盘共有 19×19 个点,每个点有『无子』、『黑子』、『白子』三种可能性。不考虑无气提子等特殊情况,则一共有 3^361 种盘面。如果考虑到下子进程,则有 361! 种棋谱。

因为有围棋规则在,实际数字会小一些,但这不是本文重点。这两个数字分别是一个 173 位数和一个 769 位数:

我故意设置了不换行,这样大概能直观地体会这个数字有多大了。(左上角的控制键切换换行与展开)

呼应本文标题的问题来了——这两个数字末尾各有多少个『0』?

你当然可以靠眼力劲儿去数,前者容易看出末尾没有 0,后者大概费些功夫能数出有 88 个 0。当然你也可以使用查找替换,数起来方便些。

但是如果没有事先把总数算出来,又如何数出一个数的末尾有多少个 0 呢?毕竟连乘 300 多次算个 700 多位的数字恐怕是更累的一件事情。能少算就少算点吧。

 

办法是有的,数质因素 5 就可以了。

要注意到,无论多少个数连乘,只有 2×5 才会在末尾添加一个 0。有人说 8×5 也会出 0,4×25 会出两个 0。但 8×5=40=22x2x5,有两个 2 其实浪费掉了。而 4×25 = (2×5)2,本质上正好是两对 2×5 相乘,完全符合之前的设定。又因为在阶乘中,2 作为质因数的出现次数远远超过质因数 5 出的次数。每个偶数都能至少贡献一个质因素 2,而每个 5 个数字才能贡献一或若干个质因数 5。因此可得结论:

只要数清连乘中一共有多少个质因数 5,就知道最终数字末尾有多少个 0 了。

对于 3^361,显然一个质因数 5 都没有。所以末尾没有 0。

对于 361!,

  • 每隔 5 个数字,可以提供一个 5。即 5, 10, 15, 20, 25, 30, ……, 360。一共 361 / 5 向下取整,有 72 个。
  • 每隔 25 个数字,可以一次提供两个 5。即 25, 50, 75, ……。一共 361 / 25 向下取整,有 14 个。由于上一条已经重复计算一次,因此这里的 14 不必再翻倍了。
  • 每隔 125 个数字,可以一次提供三个 5。即 125, 250。一共 361 / 125 向下取整,有 2 个。由于上一条已经重复计算一次,因此这里的 2 不必再翻倍了。

再上去是 625,直接超了。于是数 5 活动就此停止。

一共有 72+14+2=88,而 2 的数量肯定是足够的,于是会产生 88 组 2×5,即末尾有 88 个『0』。

这个方法可以广泛用于各类无聊的数 0 活动中,例如:

任取一个足够大的数字 N,比如 10100 即 1 googol,把小于 N 的所有素数乘起来,那么多素数的乘积的末尾有几个 0?

——答案是只有一个 0,算对了么?

 

那么第二个问题来了,为什么数 5 知 0?

答案是,这个和 10 进制有关。

仔细思考,『进制』的本义就是每满多少就 归 0 进位。换句话说,如果 要让末尾为 0,就必须不多不少,最末尾那些余量恰恰等于当前进制。这个 『余量』不是严谨的用词,意会即可。在 10 进制里,你总要正好凑出 10 个或者 10 的倍数个,才能让末尾是 0。在 8 进制里就要凑 8 的倍数个让末尾是 0。16 进制凑 16,N 进制凑 N。

所以归根结底,要让若干个数连乘得到末尾零,就是看能凑出几份当前进制。10 进制就是要凑 2×5,8 进制要凑 2x2x2,每三份质因数 2 会多一位尾 0,只看 2,别的都没用。

既然 10 进制下,10 的唯一质因数分解就是 2×5,而 2 又远多于 5,所以数 5 知 0 就变成了最简单的办法。

理解了这些,下面这些问题也不难回答了:

3361在 3 进制下,末尾有几个 0?

答案是 361 个 0。这个问题等效于 10 进制下 10361末尾有几个 0,等效于 N 进制下 N361末尾有几个 0。——都是361个。

21024在 16 进制下,末尾有几个 0?

答案是 256 个。因为 16 = 24,1024 / 4 = 256。

最后一个问题:

31024在 2 进制下,末尾有几个 0?