ABC備忘録[ABC161 C - Replacing Integer] (Python)

ABC161 C - Replacing Integer

問題文

青木君は任意の整数$x$に対し、以下の操作を行うことができます。

操作

$x$を$x$と$K$の差の絶対値で置き換える。

整数 Nの初期値が与えられます。この整数に上記の操作を0回以上好きな回数行った時、とりうるNの最小値を求めてください。

制約

$0≤N≤10^{18}$
$1≤K≤10^{18}$
入力は全て整数

C - Replacing Integer

解法

行う操作は、例えば$N=7$、$K=4$のとき$x$から$K$を差分の絶対値が最小になるまで引くことなので、$x=7,x=3,x=1,x=3$と$x$が変化していく。
よって求める$x$は$1$となる。
なお、$x=1$以降は$x$は$1$と$3$を繰り返す。

ただこの操作を$N$と$K$が大きいときに愚直に繰り返すと大変なので、求める最小値は$N/K$の余りか$K - (N/K)$の余りであることを利用する。

N, K = map(int,input().split())

print(min(N % K, K - (N % K)))

間違いがある場合は指摘してください。