公式解説に載っていなかったので。多分邪道で、公式解説の方が普通に筋がいいと思います。
問題
概要
- $T$件のテストケースについて、以下の問題を解け。
- 正整数$A,B$が与えられる
- 非負整数$X,Y$で、$B+Y$が$A+X$の倍数となるようなものについて、 $X+Y$の最小値を求めよ。
制約
- $1 \leq T \leq 100$,
- $1 \leq A, B \leq 10^9$.
解説
まずは $A \geq B$の場合について。これは簡単で、$B$が$A$に等しくなるように$Y=A-B$とし、$X=0$としたときが$X+Y$が最小になる。ほとんど自明だが、$X > 0$と仮定すると $A \geq B$より $A+X > B$. このとき、$Y$を最小にするには $A+X=B+Y$として1倍の倍数にするほかないが、この時$Y=A+X-B$となり明らかに当初の$X=0$としたときの$Y=A-B$よりも大きくなってしまう。そのため、単に$A-B$を出力すればよい。
難しいのは $A < B$のとき。この問題を解く上で許容される計算量について考えてみると、$1 \leq T \leq 100$の条件から、1テストケースあたり最大で$O(10^7)$程度が求められる1。したがって、$O(A)$や$O(B)$の解法は許容されない。
Aが100000以下のとき
一旦計算量を無視して愚直な解法について考えてみる。
最も簡単な解法は、$X$を固定すれば$B+Y$が$A+X$の倍数になるような最小の$Y$は簡単に求めることができる2ので、$X$を全探索することだろう。$X$をどの範囲で探索すればよいかについてだが、$X=0$のとき、最小の$Y$は $(A-B \mathrm{mod} A)
\mathrm{mod} A$で求めることができる。これは明らかに$A$で上から押さえることができるので、$X+Y$の最小値は最大でも$A-1$であることがわかる。したがって、$X$について$0$から$A-1$までの範囲を全探索すれば、$X+Y$の最小値を$O(A)$で計算できる。
この方法では$A$が大きいときに対応できないので無意味に思えるが、少なくとも$A \leq 10^5$のような範囲では、明らかに有効といえる。つまり、$10^5 \leq A$ のときに他の方法で高速に$X+Y$の最小値を求めることができればよい。
Aが100000より大きいとき
この場合には、先ほどの$X$で全探索する方法は使えない。$O(A)$の解法は計算量が大きくなりすぎてしまうからである。ここで、前提条件から$A < B$であり、なおかつ$B \leq 10^9$であることを思い出そう。ここからわかることは$B/A$が最大でも$O(10^4)$くらいで収まるということである。改めてこの場合で$X=0$を仮定する。この時、$B+Y$が$A$の倍数になるということだから、ある正の整数$r$を用いて、$B+Y=rA$と書ける。式変形をすると $Y=rA-B$となり、この時$Y$を最小にしたいのだから$r$は$rA-B$が$0$以上となるような最小の$r$を選ぶのが妥当である。これはまさに$B/A$とオーダーが等しいわけで、$r$はどれだけ大きくても$O(10^4)$で押さえられることになる。
したがって、各$r$について$X+Y$の最小値を$O(1)$で求められるなら、$r$の全探索が間に合うことになる。
実際、以下の議論から、$r$を決め打ちしたときの最も$X+Y$を小さくするような$X$と$Y$を$O(1)$で求めることができる。
$r$を決め打ちしたとき、$Y+B$が$X+A$の倍数になるという条件から、以下の等式が成り立つ。
Y+B = r(A+X).
これを$Y$について解くと$Y=rA+rX-B$となる。ここで$Y$が非負という条件から$rA+rX-B \geq 0$が成り立つ必要がある。これを$X$について解くと、$X \geq (B-rA)/r$となる。ここでさらに$Y=rA+rX-B$について考えると、$Y$は$X$の一次関数になっており、その傾きは正だから、$Y$は$X$について単調増加する。したがって、$X$がとりうる最小の時に$Y$も最小となり、このときが$X+Y$も最小となる。したがって、$X$の最小値を求めれば、$r$を決め打ちしたときの$X+Y$の最小値もわかることになる。
$X \geq (B-rA)/r$は、$B-rA < 0 $のときに$X$が非負の条件から$X=0$とするのが最適であることに注意すれば、各$r$について$X+Y$の最小値を$O(1)$で求められる。したがって、$r$について全探索すれば$r$は最大で$O(10^4)$程度だから十分高速に$(X+Y)$の最小値を求められる。
結論
$A$が$10^5$くらいよりも小さいか大きいかで場合分けをする。
- 小さいなら$X=0$のときの$X+Y$が$A$で押さえられることに注目して、$X$について$0$から$A-1$の範囲で全探索を行う
- 大きいなら、$B/A$が最大でも$O(10^4)$程度で押さえられることに注目し、$B+Y$が$A+X$の$r$倍になるとして$r$について全探索を行う
提出コード