数学—倍数巧算

· · 算法·理论

题外话：这几天嘞一直在搞初赛，脑子塞了好多东西，快MLE了，故写一篇博客来当备忘录吧。（也老久没更新了啊哈哈哈哈哈）

一、关于 2 和 5 , 4 和 25 ,8 和 125 ……的倍数

结论： 2 和 5 倍数需看末一位能否被 2 或 5 整除， 4 和 25 的倍数需看末两位能否被 4 或 25 整除， 8 和 125 的倍数需看末三位能否被 8 或 125 整除……(以此类推)。

证明：以 2 和 5 为例：

比如说判断 123546789 是否为 2 的倍数？是否为 5 的倍数？

所以我们可以将 123456789 拆分为 12345678 \times 10 + 9 （位值原理）。

因为 2 \times 5=10

所以 12345678 \times 10 一定为 2 或 5 的倍数.

所以最后只需要判断最后一位能否被 2 或 5 整除啦~

那 4 和 25 , 8 和 125 又怎么办呢？

其实很简单的，

从 2 到 4 是乘了 2 ，从 5 到 25 乘了 5 ，

整体乘 10 ，

所以需要多考虑一位啦~

问题解决~

二、关于 3 和 9 的倍数

结论：判断是否为 3 或 9 的倍数需将所有位数数字相加，结果为 3 或 9 的倍数，原数为 3 或 9 的倍数。

证明：

比如判定 123456789 为例，

可以拆解为 1 \times 100000000 + 2 \times 10000000 + 3 \times 1000000 + 4 \times 100000 + 5 \times 10000 + 6 \times 1000 + 7 \times 100 + 8 \times 10 + 9 ，

同时也可以变成 1 \times ( 99999999 + 1 )+ 2 \times ( 9999999 + 1 )+ 3 \times ( 999999 + 1 ) + 4 \times ( 99999 + 1 ) + 5 \times ( 9999 + 1 ) + 6 \times ( 999 + 1 ) + 7 \times ( 99 + 1 ) + 8 \times ( 9 + 1 ) + 9 ，

这时 999……9 必为 3 或 9 的倍数，

所以只需要判断 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 是否为 3 或 9 的倍数。

问题解决 \times 2 ~

三、关于 11 的倍数

结论：判断是否为 11 的倍数需将奇数位上的数字之和与偶数位数字之和的差(奇数位与偶数位判断需从个位开始数)能被 11 整除，那么原数就能被 11 整除。

证明： 比如 123456789 ，

可以拆解为 1 \times 100000000 + 2 \times 10000000 + 3 \times 1000000 + 4 \times 100000 + 5 \times 10000 + 6 \times 1000 + 7 \times 100 + 8 \times 10 + 9 ，

同时也可以变成 1 \times ( 99999999 + 1 ) + 2 \times ( 100000001 - 1 ) + 3 \times ( 999999 + 1 ) + 4 \times ( 1000001 - 1 ) + 5 \times ( 9999 + 1 ) + 6 \times ( 1001 - 1 ) + 7 \times ( 99 + 1 ) + 8 \times ( 11 - 1 ) + 9 ，

这时 999……9 (偶数个 9 )和 1000……01 (奇数个 0 )必为 11 的倍数，

所以只需要判断 \lvert 1-2+3-4+5-6+7-8+9 \rvert 是否为 11 的倍数。

问题解决 \times 3 ~

四、关于 7 ， 11 和 13 的倍数

结论：判断是否为 7 ， 11 和 13 的倍数需将该数的末三位与末三位以前的数之差是否为 7 ， 11 和 13 的倍数

证明： 比如 123456789 ，

可以拆解为 123456 \times 1000 + 789 ，

同时也可以变成 123456 \times (1001 - 1 ) + 789 ，

即为 123456 \times 1001 - 123456 + 789 ，

这时1001必为7，11和13的倍数，

所以只需要判断 \lvert -123456 + 789 \rvert 是否为11的倍数。

问题解决 \times 4 ~

五、关于 999……9 的倍数

结论：判断是否为 999……9 (n个 9 )的倍数需将该数从末为开始n位n位一分，依次相加所得的数是否为 999……9 的倍数

证明： 比如 123456789 是否为 99 的倍数，

可以拆解为 1 \times 100000000 + 23 \times 1000000 + 45 \times 10000 + 67 \times 100 + 89 ，

同时也可以变成 1 \times (99999999 + 1) + 23 \times (999999 + 1) + 45 \times (9999 + 1) + 67 \times (99 + 1) + 89 ，

这时 999……9 必为 99 的倍数，

所以只需要判断 1 + 23 + 45+ 67 + 89 是否为 99 的倍数。

问题解决 \times 5 ~

总结：

其实这类问题大部分都是运用位值原理和乘法分配律通过“凑”的方式“凑”出倍数，然后进行计算。

（这条博客仅是本人对比较常见的数字倍数的一个笔记，有补充或错误欢迎指出）

完美解决~~~~~