[公布原理]由七夜抽奖规则想到的：大数是否能被7整除的三种判断方法

blow201

原帖由 tonylmd 于 2009-4-22 12:44 发表 看到七大爷的最新抽奖规则 联想到这个是同桌教俺的~随便选一个 39477158为例子方法一：把大数从个位开始 每三个数分一段39 477 158奇数段的和 减 偶数段的和（39+158）-477=-280如果计算结果能被7 ...

这个能证明一下么，刚才试了一下，没证出来。。。

tonylmd

答案是肯定的~
等大家研究下嘛…

icylemon

直接证明貌似不是很容易，但可以编程验证一下～
比如第一种方法可以用下面的思路
随机输入数x，检查数字的位数，然后除以1000取余数，记做a[0]，继续除，余数记做a[1]，一次类推，直到不能继续除为止。然后对一维数组a的奇数项和偶数项分别加和再作差，记做b，用7除b取余，然后用7除x取余，看两个数是否都为0，若都为0，则方法正确～
其他方法思路类似～

Cielo

方法一和二本质上是一样的，利用 1001 可以被 7 整除：
1000^(2k) x a = (-1)^2k x a = a (mod 7)
1000^(2k-1) x b = (-1)^(2k-1) x b = -b (mod 7)

方法三：
如果 10a+b 可以被 7 整除，那么 3a+b 也可以被 7 整除，
所以 a-2b = (10a+b) - 3 x (3a+b) 也可以被 7 整除！

tonylmd

呃…楼上厉害~

shifujun

这个真是头一次听说,好方法.

kexin_xiao

LZ明显帮老七做广告!

tonylmd

哇~看14#和16#就知明显不是嘛~

lulijie

一个n位数，表示成  a(n)a(n-1)a(n-2)......a(3)a(2)a(1)     
求它除以 m  的余数。
简便的方法就是 找到一个数，可以表示成 10^k+1  或 10^k-1 的形式  它除以 m 的余数是0。
一：10^k+1 除以 m 余数是0   
     那么   a(n)a(n-1)a(n-2)......a(3)a(2)a(1)   除以 m  的余数  就等于
              a(k)a(k-1)......a(2)a(1)-a(n)a(n-1)......a(k+2)a(k+1)    除以 m  的余数
      比如 m=11        k=1
           求  123456789 除以 11余数
           123456789 ≡ 9-12345678 =9-(8-1234567)=9-8+1234567=9-8+7-123456 (mod 11)
            ≡ 9-8+7-6+12345=......=9-8+7-6+5-4+3-2+1   (mod 11)
           对于11来说，除以它的余数，就等于奇数位的和减去偶数位的和除以11的余数。
      比如 m=7         k=3   （因为1001整除7）  
          比如   39477158  除以7的余数
            39477158 ≡ 158-39477≡ 158-477+39 （mod 7）     就是楼主举的例子。
      比如 m=13        k=3   （因为1001整除13）  
          同7相同。
          39477158 ≡ 158-39477≡ 158-477+39 （mod 13）
二：10^k-1 除以 m 余数是0   
    那么   a(n)a(n-1)a(n-2)......a(3)a(2)a(1)   除以 m  的余数  就等于
              a(k)a(k-1)......a(2)a(1)+a(n)a(n-1)......a(k+2)a(k+1)    除以 m  的余数
        比如 m=9或3        k=1
             求1234567 除以  9的余数
              1234567 ≡ 7+123456≡7+6+12345≡7+6+5+1234≡......≡7+6+5+4+3+2+1  (mod 9)
            对于9或3来说，除以它的余数，就等于所有位数的和除以9或3的余数。
        比如 m=37        k=3
            求123456789 除以 37的余数
              123456789≡789+123456≡789+456+123  (mod 37)

tonylmd

好久没见lulijie喔~
有点晕…明天和同桌研究研究…