難しい 0件解決済み 正答率0%

最長の循環節

上限以下の d のうち、1/d の循環節が最も長くなるものを求めます。

このチャレンジで学べること

  • 余りを使って筆算の割り算をシミュレートできる
  • 表を使って繰り返しを検出できる
  • 最初に現れた位置から循環の長さを求められる

問題

原文(英語)を表示

単位分数には、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

例

例 1
入力:
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 です。

例 2
入力:
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用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。