\(K=0\) のとき、答えは \(N^2\) です。以降、そうでない場合を考えます。

\(b\) を全探索すると、\(a\) としてあり得るものの個数は \(\sum_{i=0}^{b-K-1} \lfloor \frac{N-K+b-i}{b}\rfloor\) となり、これはFloor Sumそのものです。(ただし、\(K=0\) のときは正整数でない \(0\) をカウントしてしまい、成り立ちません)

計算量は定数倍の軽い \(O(N \log N)\) となり、十分間に合います。