問題
単位分数には、1/4 = 0.25 のように割り切れるものと、同じ数字の並びを永遠に繰り返すものがあります。1/6 = 0.1666... は1桁の循環節を、1/7 = 0.142857142857... は6桁の循環節を持ちます。d = 2, 3, ..., limit のうち、1/d の循環節が最も長くなる d を求めてください。筆算の割り算をコードで再現しましょう。同じ余りが再び現れた時点で、数字の繰り返しが始まります。
longest_recurring_cycle(limit) を実装してください。
入力
limit:試す分母の最大値。
出力
循環節が最も長い d を返してください。割り切れる分数の循環節の長さは 0 とします。同じ長さの d が複数あれば、最小のものを返します。
制約
2 ≤ limit ≤ 2000
例
入力:
limit = 8
期待される出力:
expected = 7
入力:
long long limit = 8;
期待される出力:
long long expected = 7;
入力:
long limit = 8;
期待される出力:
long expected = 7;
解説
2 から 8 の循環節の長さは 0, 1, 0, 0, 1, 6, 0 なので、答えは 7 です。
入力:
limit = 5
期待される出力:
expected = 3
入力:
long long limit = 5;
期待される出力:
long long expected = 3;
入力:
long limit = 5;
期待される出力:
long expected = 3;
解説
1/3 は1桁が繰り返し、1/2、1/4、1/5 は割り切れるので、答えは 3 です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
1/d の新しい桁は、余りに 10 を掛けたものから得られます。
ヒント 2
各余りが最初に現れたステップを記録しておきます。
ヒント 3
余りが 0 になれば小数は割り切れます。そうでなければ、同じ余りが2回現れたステップの差が循環節の長さです。
目安の計算量
時間 O(limit²)、追加メモリ O(limit)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。