AtCoder Regular Contest 150 B問題 Make Divisible

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$(B+Y)$ が $(A+X)$ の倍数であるという条件下における $(X+Y)$ の最小値を求めよ.

$T$ ケースのマルチケース

制約

$1 \leq A, B \leq 10^9$
$1 \leq T \leq 100$

解法

$X$ を固定する. このとき, $(B+Y)$ が $(A+X)$ の倍数になるような最小の非負整数 $Y$ を $Y_X$ と書くことにする.

$A \geq B$ のとき

このとき, $A+X \geq B$ であるから, $(B+Y)$ が $(A+X)$ の倍数であるとき, $Y$ を最小にするためには $B \geq 1$ であるから, $B+Y_X=A+X$ でなくてはならない. よって, $Y_X=X+(A-B)$ である. よって, $X+Y_X=X+(A+X-B)=2X+(A-B)$ である. $X$ は非負整数を任意にとすることができるので, $X=0$ とすると $X+Y_X$ を最小にすることができ, このとき, $X+Y_X=0+(A-B)=A-B$ である.

$A\lt B$ のとき

一般に, 整数 $n$ を正の整数 $m$ で割った余りが $r$ であるとき,

$r=n-m \left \lfloor \dfrac{n}{m} \right \rfloor$

が成り立つ.

よって, 各 $X$ に対して, 余りに着目することで, $(B+Y_X)$ が $(A+X)$ の倍数であるような最小の非負整数 $Y_X$ は

$Y_X=\begin{cases} 0 & ( (A+X) | B ) \\ (A+X)-\left(B- (A+X) \left \lfloor \dfrac{B}{A+X} \right \rfloor \right) & ( (A+X) \not | B) \end{cases}$

である.

$B$ が $(A+X)$ の倍数の場合

この場合, $Y_X=0$ である. そして, $(A+X)$ は $B$ の約数である. $X+Y_X=X$ であるから, このような $(A+X)$ が $B$ の約数になるような最小の非負整数 $X$ を取るべきである. これは $B$ の $A$ 以上の最小の約数を $D$ としたとき, $X=D-A$ である.

$B$ が $(A+X)$ の倍数ではない場合.

この場合,

$Y_X=(A+X)-\left(B- (A+X) \left \lfloor \dfrac{B}{A+X} \right \rfloor \right) =(A+X) \left(1+ \left \lfloor \dfrac{B}{A+X} \right \rfloor \right)-B$

である.

$\left \lfloor \dfrac{B}{A+X} \right \rfloor=Q$ であるような $X$ をまとめて考える. このとき,

$X+Y_X=X+(A+X)(1+Q)-B$

であるから, $X$ として, $\left \lfloor \dfrac{B}{A+X} \right \rfloor=Q$ を満たすような最小の非負整数を取るべきである.

また, $\left \lfloor \dfrac{B}{A+X} \right \rfloor=Q$ を満たすような $A+X$ の範囲は2つの整数 $L_Q, R_Q$ *1 に対して, $L_Q \leq A+X \leq R_Q$ となる. よって, $L_Q-A \leq X \leq R_Q-A$ である. よって, $0 \leq R_Q-A$ のとき, 非負整数 $X$ が存在して, 最小値は $\max(0, L_Q-A)$ である.