c++ - 检查二进制数是否能被 13 整除

Question

如果用户输入从最高位到最低位的数字，如何检查二进制数是否可以整除 13？

位数可能非常大，因此将其转换为十进制然后检查其可整除性是没有意义的。

我已经以常规方式处理了它。位数最多为 10^5，因此在将其转换为十进制时会产生溢出。

如何解决这个问题？示例:

110010000100100它是除以 13

111111111111111它不能被 13 整除

Answer 1

这是一个 O(N) 算法:

从左到右遍历位。每增加一个位置相当于将当前值乘以 2，然后加上 0 或 1。这在模 13 算术中也是如此。当你到达最后一位时，看看最终值是否等于 0。如果是，那么原始数字可以被 13 整除。