問題
数を、その各桁の階乗の和で置き換えます。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
例
入力:
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 です。
入力:
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用に調整されています。上記の説明と制約に従ってください。