この問題は、調和級数の和の性質と、累積最小値を用いることで で解くことができます。
問題文を少し簡単にするために、以下のように定義される関数 について考えます。
- となる非負整数 における、 の最小値
と の値を全探索することで、 から すべての値を篩の要領で求められます。
となる の組の全探索は で処理できます。
関数 が求まったので、関数 の定義を以下のように言い換えることができます。
- となる非負整数 における、 の最小値
ここで とおくと、 は以下のようになります。
これを愚直に計算すると になりますが、
として、が小さい方から累積最小値をとっていくことで、 で計算できます。
よってこの問題は で解くことができます。
(スタックオーバーフローに注意してください)
解答例(C++)
解答例(Python)