37 で割り切れるかを調べる
- 割り切った関係 (Garbage Collection)
既にコメント欄でみきぬさんが正解を書いてしまっていますが、一応。
この手の問題は、まずは幾つかの実例を調べてみて、そこから規則性を見つけるってのがセオリーかなと思います。
今回は、こんな感じで書き出して見ました。
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