……数零与进位
最近 AlphaGo 与李世石的人机围棋大赛很火，也蹦出一大波跳梁小丑。你会发现什么热点事件都少不了这种人，总是挡在路上污人视线，比如那个输入法王。我记得上次 SoloLens 它也跳出来大谈 Matrix 来着。
牢骚完毕，这次深夜短篇不是写围棋也不是写计算机的，只说数数，更严格的说，只是数『0』。比如：
围棋棋盘共有 19×19 个点，每个点有『无子』、『黑子』、『白子』三种可能性。不考虑无气提子等特殊情况，则一共有 3^361 种盘面。如果考虑到下子进程，则有 361! 种棋谱。
因为有围棋规则在，实际数字会小一些，但这不是本文重点。这两个数字分别是一个 173 位数和一个 769 位数：
1 | 3^361=17408965065903192790718823807056436794660272495026354119482811870680105167618464984116279288988714938612096988816320780613754987181355093129514803369660572893075468180597603 |
呼应本文标题的问题来了——这两个数字末尾各有多少个『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？