如何知道一个二进制数能否被 9 整除？

Question

不做进制转换，如何知道？

Answer 1

用自动机做除3
包含三个状态
s0 为 余0 集合
s1 为 余1 集合
s2 为 余2 集合
从s1 开始
转移规则

     s0 1 -> s1; 0 -> s0
     s1 1 -> s0; 0 -> s2
     s2 1 -> s2; 0 -> s1

记录商
每次超过3则记为1 即转移过程时

 s1 -> 1 , s2 -> 1 ,s2 -> 0

最后商排列一下就是
然后把商重新进行一次计算 如果最后状态为s0 则被9整除

拿楼上举例
100010101 从做到右扫描 状态经历

   0     0(1)     0      1(1)     0(1)     1(1)     0     1
s1 -> s2  ->   s1 ->  s2  ->   s2  ->   s1  -> s0   -> s0 -> s1 

商为 1011100
因为在s1 所以不能被3整除 自然不能给9整除

修改一下为 0
100010100 则最后为 s0 -> s0 能整除 结果为1011100
再进行一次计算

   0     1     1     1     0     0
s1 -> s2 -> s2 -> s2 -> s2 -> s1 -> s2  

在状态s2 所以该数无法被9整除

转移状态你可以自己想一下为何是这样 程序你也可以自己想一下如何写 - -