この問題は、調和級数の和の性質と、累積最小値を用いることで で解くことができます。

問題文を少し簡単にするために、以下のように定義される関数 について考えます。

  • となる非負整数 における、 の最小値

の値を全探索することで、 から すべての値を篩の要領で求められます。
となる の組の全探索は で処理できます。   

関数 が求まったので、関数 の定義を以下のように言い換えることができます。

  • となる非負整数 における、 の最小値

ここで とおくと、 は以下のようになります。

これを愚直に計算すると になりますが、

として、が小さい方から累積最小値をとっていくことで、 で計算できます。

よってこの問題は で解くことができます。

(スタックオーバーフローに注意してください)
解答例(C++)
解答例(Python)