A+BC

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

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

• $x=A×B$ となる非負整数 $A,B$ における、$A+B$ の最小値

$A$ と $B$ の値を全探索することで、$g(0)$ から $g(N)$ すべての値を篩の要領で求められます。
$A×B \leq N$ となる $A,B$ の組の全探索は $O(NlogN)$ で処理できます。 　　

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

• $x=A+P$ となる非負整数 $A,P$ における、$A+g(P)$ の最小値

ここで $P=x-A$ とおくと、$f(x)$ は以下のようになります。

$f(x)=min_{0\leq A \leq x}($ $A+g(x-A)$ $)$

これを愚直に計算すると $O(N^2)$ になりますが、

$f(x):=min(f(x-1)+1, g(x))$

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

よってこの問題は $O(NlogN)$ で解くことができます。

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