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

桁の階乗の連鎖

桁の階乗の連鎖に含まれる異なる項の個数が、ちょうど指定された数になる開始値を数えます。

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

  • 値が繰り返されるまで連鎖をたどれる
  • ループ内とループに入る前の連鎖の長さを求められる
  • 保存した長さを再利用できる

問題

原文(英語)を表示

数を、その各桁の階乗の和で置き換えます。145 は 1! + 4! + 5! = 145 で元に戻り、69 は 6! + 9! = 363600 になります。これを繰り返すと、必ずループに入ります。開始値の連鎖とは、最初に項が繰り返されるまでの項の列のことです。69 なら 69, 363600, 1454, 169, 363601 と進み、次に再び 1454 になるので、異なる項は5個です。1 から limit までの開始値のうち、連鎖の異なる項がちょうど length 個になるものを数えてください。

digit_factorial_chains(limit, length) を実装してください。

多くの連鎖は同じ数に行き着きます。各数の連鎖の長さがわかったら保存しておき、再利用しましょう。

入力

limit:開始値の最大値。

length:求める異なる項の個数(開始値を含みます)。

出力

1 ≤ n ≤ limit を満たす開始値 n のうち、連鎖の異なる項がちょうど length 個であるものの個数を返してください。

制約

1 ≤ limit ≤ 100,000; 1 ≤ length ≤ 70

例

例 1
入力:
limit = 2
length = 1

期待される出力:
expected = 2
入力:
long long limit = 2;
long long length = 1;

期待される出力:
long long expected = 2;
入力:
long limit = 2;
long length = 1;

期待される出力:
long expected = 2;

解説

1! = 1、2! = 2 なので、1 と 2 はそれぞれ自分自身に移り、連鎖は1項です。答えは 2 です。

例 2
入力:
limit = 10
length = 2

期待される出力:
expected = 1
入力:
long long limit = 10;
long long length = 2;

期待される出力:
long long expected = 1;
入力:
long limit = 10;
long length = 2;

期待される出力:
long expected = 1;

解説

3 は 6, 720, 5043, ... と続くので長くなります。10 は 1! + 0! = 2 となり、その後は 2 のままなので2項です。ちょうど2項なのは 10 だけなので、答えは 1 です。

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

0! から 9! までを最初に一度だけ計算しておきます。

ヒント 2

現在の連鎖で各値が何ステップ目に現れたかを記録しておくと、繰り返しが起きたときにループの始まりがわかります。

ヒント 3

ループ内の値はすべてループの長さを持ち、ループに入る前の各値は次の値より1だけ長くなります。

目安の計算量

時間 O(limit × log limit)(メモ化を使う場合)、追加メモリ O(limit)

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

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

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

他の人の解答から学ぶ

コミュニティの解答

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