前言

今天因为力扣上一道题 FizzBuzz 而想到了一个问题。

判断一个数能否被 2 整除，只要看个位；判断一个数能否被 3 整除，主要看各位之和。

那么，如何快速判断一个数能否被 2，3，4，5，6，7，8，9 整除，有没有什么快速算法？

答案是肯定的。看完这篇文章。只需 5 分钟，你就能学会一辈子都能用的快速判断个位数整除问题技能。

简单的情形

先给出一些简单情况下的答案

• 能否被 2 整除

判断个位数是否为 2 的倍数

• 能否被 3 整除

判断各位之和是否为 3 的倍数，再转化为判断各位之和的各位之和是否为 3 的倍数......

• 能否被 5 整除

判断个位数是否为 0 或 5

• 能否被 6 整除

判断能否被 2 整除且能否被 3 整除

• 能否被 9 整除

判断各位之和是否为 9 的倍数，再转化为判断各位之和的各位之和是否为 9 的倍数......

稍微复杂的情形

然后分析稍微复杂的情形

• 能否被 4 整除

因为 100 % 4 === 0

任意一个数又可以拆分为 100 的整数倍 加上 一个二位数

所以只需判断最后两位是否为 4 的倍数

• 能否被 8 整除

因为 1000 % 8 === 0

任意一个数可以看作 1000 的整数倍 加上 一个三位数

所以只需判断最后三位是否为 8 的倍数

• 能否被 7 整除

这个我个人想不出来简便法。上网搜了一下，学会了很犀利的两招，组合使用很强大

• 首先是截尾法：

  可以截断原数的个位数，然后判断 截断后的数 - 个位数 x 2 能否被 7 整除

  比如：

  91 能否被 7 整除，等价于 (9 - 2 = 7) 能否被 7 整除

  789 能否被 7 整除，等价于 (78 - 18 = 60) 能否被 7 整除

  4221 能否被 7 整除，等价于 (422 - 2 = 420) 能否被 7 整除，等价于 (42 - 0 = 42) 能否被 7 整除

• 然后是三位数减法

  从右到左，假设每 3 位数为 1 节，将奇数节上所有三位数之和减去偶数节上所有三位数之和，然后判断所得结果能否被 7 整除

  比如：

  123456 能否被 7 整除，等价于 (456 - 123 = 333) 能否被 7 整除，然后根据截尾法，(33 - 6 = 27) 能否被 7 整除

  35147128639 能否被 7 整除，等价于 (639 + 147 - 128 - 35 = 623) 能否被 7 整除，然后根据截尾法，(62 - 6 = 56) 能否被 7 整除

题外话

一. 组合技

如果你以为学会了个位数整除的算法就只能对付这 9 个数，那就大错特错了。

看下面几个问题：

• 116 能否被 12 整除？

12 = 3 * 4，116 能被 12 整除等价于 116 能被 3 整除 且 116 能被 4 整除

116 不能被 3 整除，所以 116 不能被 12 整除

• 189 能否被 21 整除？

21 = 3 * 7

189 能被 3 整除，也能被 7 整除，所以 189 能被 21 整除

• 225 能否被 35 整除？

35 = 5 * 7

225 能被 5 整除，不能被 7 整除，所以 225 不能被 35 整除

总结一下，如果除数能被拆分成 2-9 之间互质的多个数相乘，那么我们仍可以组合运用简便算法。

二. 乘法逆元

记得我之前写的一篇 博客，里面提到的一个技巧这里也用得上

假设有一个大数 A，有一个小数 B，想知道 A % B 的结果，可以用以下算法：

• 列出所有对 B 取模余 1 的数 {B1, B2, ...} (也即：B*1+1, B*2+1, ...)
• 如果大数 A 的因式含有 B1, B2, ... 这样的数，那么 A 约去这个数后对 B 求余结果不变

比如 100 % 12 = ？

• 12 取余为 1 的数为： {13， 25， 37， 49， ...}
• 100 是 25 的倍数，100 / 25 = 4

故 100 % 12 = 4 % 12 = 4

虽然这不是万金油解法（人家本来也不干这个），但是显然，这也是解决整除问题的强力手段