感謝您提出這個問題,使我們重新去深入探討. 對於較大的被除數與除數,例如檢查一個千位以上的數是否為37879的倍數時,在此提供神豬算法,盼能彼此切磋. 首先: 1.mod(a,b)代表a除以b所得之餘數 2.(a1,a2,.....an)*(b1,b2,....bn)=a1b1+a2b2+.....anbn
舉7的倍數而言: (i)mod(1,7)=1 mod(10,7)=3 mod(10^2,7)=2 mod(10^3,7)=6 mod(10^4,7)=4 mod(10^5,7)=5 mod(10^6,7)=1..............
將餘數1~6按位數順序組合成(5,4,6,2,3,1) 將給定任意數以個位數起分組形成(a1,a2,a3,a4,a5,a6),(b1,b2,b3,b4,b5,b6)....,位數不夠可以補零 例如1234567812345678可以形成(0,0,1,2,3,4),(5,6,7,8,1,2),(3,4,5,6,7,8)三組 將各組視為向量,與餘數組(5,4,6,2,3,1)內積所得總和,檢查是否為7的倍數 mod[(0,0,1,2,3,4)*(5,4,6,2,3,1) , 7]=2 mod[(5,6,7,8,1,2)*(5,4,6,2,3,1) , 7]=0 mod[(3,4,5,6,7,8)*(5,4,6,2,3,1) , 7]=4 mod(2+0+4 , 7)=6,因此 mod(1234567812345678 , 7)=6
(ii)檢查向量(5,4,6,2,3,1)其中5+2=4+3=6+1=7 mod[(5,6,7,8,1,2)*(5,4,6,2,3,1) , 7] =mod[(-3,5,5,0,0,0)*(5,4,6,2,3,1) , 7] =mod[(0,0,0,3,-5,-5)*(5,4,6,2,3,1) , 7]=0 亦即mod[(5,6,7,8,1,2)*(5,4,6,2,3,1) , 7] =mod{[(5,6,7)-(8,1,2)]*(5,4,6) , 7} =mod{[(8,1,2)-(5,6,7)]*(2,3,1)] , 7}=0 因此對於7和13的倍數判斷通常我們將三位拆成一組,求奇數位組總和與偶數位數總和之差來判斷
(iii)看似麻煩,然而,對於較大的被除數與除數,除了2,3,4,5,8,9,11較為簡單外,對於除數是較大的質數時,尋求尾數判斷法,數字判斷法,間隔判斷法尋求速解在使用電腦演算時未必能一體適用或取得速度上的優勢,使用神豬向量內積法反而省事,且對於任何較大質數均可快速求解. 對任意數a,mod(10^n,a) 其中n=0~a-1,可以用EXCEL所附VB求出餘數1~a-1存放於陣列A(a)中 dim A(a):A(1)=1 for i=2 to a-1 k=A(i-1)*10 A(i)=k-a*int(k/a) next 至於將被除數以除數的位數拆成各組向量,在程式撰寫上亦很精簡,各位不妨試試. 如此,給定一個數,即可拆成多組向量,分別與A(a)這組向量求內積總和,再判斷是否為a的倍數或求出其餘數
|