[1] \(\frac{B+Y}{A+X}\) の決め打ち

\(k=\frac{B+Y}{A+X}\ (1\leq k)\) を固定した場合の \(X+Y\) の最小化について考えます。このとき \(Y=kX+kA-B,\ X+Y=(k+1)X+kA-B\) であり、\(X\) はできるだけ小さくしたほうがいいです。 \(0\leq X,\ Y\) の条件から \(X=\max(0,\ \lfloor \frac{B-1}{k} \rfloor +1 -A)\) が \(X\) の取れる最小値です。

よってこの問題は \((k+1)\max(0,\ \lfloor \frac{B-1}{k} \rfloor +1 -A)+kA-B\) が最小となる \(k\) を求める問題と言い換えられます。

[2] \(\lfloor \frac{B-1}{k} \rfloor\) の種類数の利用

上の式の値ですが、\(\lfloor \frac{B-1}{k} \rfloor\) が同じ \(k\) に対しては小さい \(k\) のほうが小さくなります。よって \(\lfloor \frac{B-1}{k} \rfloor\) がとりうる値 \(Q\) すべてに対し \(\lfloor \frac{B-1}{k} \rfloor =Q\) となる最小の \(k\) を求めて 上の式の値を計算し、その最小値を求めればいいです。\(1 \leq Q\) のとき \(Q\) に対する \(k\) の最小値は

\(Q=\lfloor \frac{B-1}{k} \rfloor \iff Q \leq \frac{B-1}{k} < Q+1 \iff \lfloor \frac{B-1}{Q+1} \rfloor + 1\leq k \leq \frac{B-1}{Q}\)

より \(\lfloor \frac{B-1}{Q+1} \rfloor + 1\) と \(O(1)\) で求まります。 \(Q=0\) に対する \(k\) の最小値は \(B\) です。

\(Q\) として考えられるのはまず \(k=1,\ 2,\ \dots,\ \lceil \sqrt{B-1}\rceil\) に対する \(\lfloor \frac{B-1}{k}\rfloor\) があります。次に \(\lceil \sqrt{B-1}\rceil < k\) に対する \(\lfloor \frac{B-1}{k}\rfloor\) ですが、これは明らかに \(\lceil \sqrt{B-1} \rceil\) 以下なので \(O(\sqrt{B})\) 通りしかありません。

以上よりテストケースあたり \(O(\sqrt{B})\) で解くことができます。