|
整数Mが整数Nで割り切れるかどうかは1/Nを筆算し、
出てくる余りをMの対応する桁に掛けてそれぞれ足した合計がNの倍数か
どうかを見ればよいようですね。理論上、何進数でもこれで行けそうです。
↑文章では説明が難しいので実例を。「864192が7で割り切れるかどうか」
1÷7=0…1
10÷7=1…3
30÷7=4…2
20÷7=2…6
60÷7=8…4
40÷7=5…5
50÷7=7…1 以下ループ
2x1 + 9x3 + 1x2 + 4x6 + 6x4 + 8x5 = 119
119は7の倍数なので864192は7の倍数です。
20÷7=3…-1 とみてもよさそうですね。
一応、原理を補足しときます〜
X進数において、整数Mが一桁の整数Nで割り切れるということは
(M mod N)=0であるということですね。
すなわち、M=Σ[k=0〜∞](Mk(X^k)) とすれば
(Σ[k=0〜∞](Mk(X^kmod N)) mod N=0
であればよいわけですから、(X^k mod N)を予め求めておく≡1÷Nを延々と
計算して余りを求めておけばNで割り切れるかどうかの判定に利用できる という仕組みです。
Nが二桁以上でも理論的には可能ですが、掛ける数がだんだん大きくなるので 実用的には限界があると思われます。」
1の余りは1
10の余りは…(10-3)+3から…3
100の余りは...((10-3)+3)*10から…30の余りで…2
1000の余りは…((100-2)+2)*10から…20の余りで…6
10000の余りは…((1000-6)+6)*10から…60の余りで…4
100000の余りは…((10000-4)+4)*10から…40のあまりで…5
1000000の余りは…((100000-5)+5)*10から…50の余りで…1
つまり…546231の繰り返し…ってことね ^^
また、1/7=142857/999999 なので、
111111 は7の倍数だから…
たとえば、
864192 なら、
111111を引いて、
753081で…
5*4+3*6+8*3+1*1=20+18+24+1=63≡0 mod 7
としてもいいけど、計算が増えるだけだったりする…^^;
|

- >
- Yahoo!サービス
- >
- Yahoo!ブログ
- >
- 練習用


