Project Euler with Ruby on WSL [Problem 26]

Level 1 達成記念

つまり雑魚

問題

Reciprocal cycles

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given: - 1/2 = 0.5 - 1/3 = 0.(3) - 1/4 = 0.25 - 1/5 = 0.2 - 1/6 = 0.1(6) - 1/7 = 0.(142857) - 1/8 = 0.125 - 1/9 = 0.(1) - 1/10 = 0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

私訳

逆数の循環節

1 < d < 1000 の範囲で、逆数 1/d の循環節が最長のものを答えよ

解答方針

筆算を実装とかは絶対やりたくない。 素因数分解して 2 or 5 しか出てこないなら…とか考えても 知りたいのは循環節の長さだから役に立たない。

小数部を 10 倍して左側に移動させてみよう。 そうすれば整数演算だけで片が付きそうだ

7 について考えると 1000000 = 7 x 142857 + 1 だ

つまり 1000000 / 7 = 142857 + 1/7 ということだ。 10 のベキを割っていって、余りが 1 になれば、循環は終了したと考えてよさそうだ。

これだけだと 6 がうまくいかない。 100 = 6*16 + 4 だし以下同様である。 しかし偶数 2n の循環節の長さは、n の循環節の長さと同じになりそうだ。 よって、初めから奇数しか考えなくてよいだろう。

…とこれだけだと実は「循環節の長さ」になっていない。なっていないのだが、 多分問題ない気がするのでそのまま行ってみる。

ダメでした

15 で死にましたね。これはたぶん 6 と同じパターン 例外的脱出規定 10%d がもう一度出現したらやっぱりそこで終わらないとだめ。

まだ駄目でした

75 で死にましたね。つまりこの場合は 100 スタートじゃないとだめなんだな