ARC150 B - Make Divisible

平方分割

問題へのリンク

まず、 B \lt A のときは X=0, Y=A-B のときに X+Y が最小となる。

以下では B \ge A のときについて考える。

X+Y

\frac{B+Y}{A+X} = k \space ( k \ge 1) とする。

このとき式変形すると、 X+Y = (k+1)X + kA - B となる。
k が固定されているとき、 X = \frac{B+Y}{k} - A であるから、 X = max( \lceil \frac{B}{k} \rceil - A, 0 ) がとりうる最小の X となる。

また、 \lceil \frac{B}{k} \rceil = \lfloor \frac{B-1}{k} \rfloor + 1 であることから、

X+Y = (k+1)max( \lfloor \frac{B-1}{k} \rfloor + 1 - A, 0 ) + kA - B を最小化すればよい。

平方分割

\lfloor \frac{B-1}{k} \rfloor が同じものについては k が小さいほうが X+Y が小さくなる。

よって、 \lfloor \frac{B-1}{k} \rfloor の取りうるすべての値について X+Y の値を求めて、最小値を得る。


i) \space k \le \lceil \sqrt{B-1} \rceil のとき
\lceil \sqrt{B-1} \rceil 通りについて、 X+Y を求める。


ii) \space k \gt \lceil \sqrt{B-1} \rceil
このとき、 \lfloor \frac{B-1}{k} \rfloor \le \lceil \sqrt{B-1} \rceil であるから、 \lfloor \frac{B-1}{k} \rfloor のとりうる値は高々 \lceil \sqrt{B-1} \rceil 通りである。
したがって、 Q = 0, ... , \lceil \sqrt{B-1} \rceil について、 \lfloor \frac{B-1}{k} \rfloor = Q となる最小の k を求めることで、 X+Y を求めることができる。

( \frac{B-1}{k} \lt Q+1 より、 k = \lfloor \frac{B-1}{Q+1} \rfloor + 1 が最小となる。)


以上のように、平方分割を利用することにより、 O( \sqrt{B} ) で各テストケースの答えを求めることができる。

提出コード


別解(?)

上と同じような考察より、 (A+X) k = B+Y の A+X, k をそれぞれ 1, ... , 10^{5} で決めうちして X+Y の値を求める。
こちらの解法の方が、上の解法をそのまま実装するよりもシンプルに実装することができた。

提出コード