普通に計算したらO(N)で間に合わないので、工夫が必要です。
k>2Nならば⌊kN⌋=1,3N<k≤2Nならば⌊kN⌋=2,⋯となるので、kが大きいところでは⌊kN⌋の値の変化は少ないです。そこで、⌊kN⌋の値が同じになるkをまとめて考えます。
mを1以上N以下の自然数とすると、⌊kN⌋=mの時m≤kN<m+1よりm+1N<k≤mNとなります。よって、⌊kN⌋=mとなるkの数は⌊mN⌋−⌊m+1N⌋となります。しかし、1≤m≤Nなので、この方法のみで計算した場合もO(N)で間に合いません。
そこで、1≤k≤Bではナイーブな方法、B<k≤Nでは上で述べた方法を使います。B<k≤Nでの⌊kN⌋の最大値はおよそBNなので、総計算量はおよそB+BNとなり、この値は相加相乗平均の不等式よりB=Nで最小値2Nをとります。よって、BをN付近の値にして上記の計算をすれば、O(N)で解を求められます。(平方分割)なお、解のオーダーはO(NlogN)なので、64ビット整数を使えばオーバーフローの心配はありません。
質問・誤りがある場合
Twitterに連絡ください。ID : @YS55749378