読者です 読者をやめる 読者になる 読者になる

雑記 - otherwise

最近はDQ10しかやっていないダメ技術者がちまちまと綴る雑記帳

37 で割り切れるかを調べる

雑談

既にコメント欄でみきぬさんが正解を書いてしまっていますが、一応。
この手の問題は、まずは幾つかの実例を調べてみて、そこから規則性を見つけるってのがセオリーかなと思います。
今回は、こんな感じで書き出して見ました。

            1 =          0 * 37 +  1
           10 =          0 * 37 + 10
          100 =          2 * 37 + 26
        1,000 =         27 * 37 +  1
       10,000 =        270 * 37 + 10
      100,000 =      2,702 * 37 + 26
    1,000,000 =     27,027 * 37 +  1
   10,000,000 =    270,270 * 37 + 10
  100,000,000 =  2,702,702 * 37 + 26
1,000,000,000 = 27,027,027 * 37 +  1

各項の余り部分に着目すると、 3 桁周期になっているのが判ります。
なので、 3 桁ずつ区切ればよさそうだな、と。
早速一般化。(上の桁を考えるときりがないので 6 桁で書いています)

         100,000 * f +       10,000 * e +     1,000 * d + 100 * c + 10 * b + 1 * a
= (99,900 + 100) * f + (9,990 + 10) * e + (999 + 1) * d + 100 * c + 10 * b + 1 * a
= 999 * (100 * f + 10 * e + 1 * d) + (100 * f + 10 * e + 1 * d) + (100 * c + 10 * b + 1 * a)

ここで 999 は 37 で割り切れるので、前半部分は無視できます。
よって式を簡略化して、

(100 * f + 10 * e + 1 * d) + (100 * c + 10 * b + 1 * a)

について考えれば OK と判ります。
で、これは何かと言えば、元の数の 3 桁ずつ区切って足し合わせたものなので、結果的に「数字を 3 桁ずつに分けて、それぞれを足した合計が 37 の倍数かどうかを調べれば良い」と云う事になります。
……って、確かに元の数を正攻法で 37 で割るよりはラクかもしれないけど、結局 3 桁の数を 37 で割る必要があるから、あまり「簡単な方法」ではないかもww