AtCoder Beginner Contest 161 C

AtCoder Beginner Contest 161 C 問題をPython で解説していきます。
まずは問題文から。
https://atcoder.jp/contests/abc161/tasks/abc161_c

C – Replacing Integer 

---

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

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

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

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

制約

• 0≤N≤10^18
• 1≤K≤10^18
• 入力は全て整数

---

入力

入力は以下の形式で標準入力から与えられる。

N K

出力

操作を 0 回以上好きな回数行った時にとりうる N の最小値を出力せよ。

解説

x と K の差の正負によって絶対値の値は変化するので，正味の操作は以下の２通りになります。

• x – K > 0 の時：x -> x – K
• x – K < 0 の時：x -> -(x – K)

なので，x – K > 0 であるときは常にx から K を引き続けていき，x – K < 0 になるまでその操作が続きます。
この操作を行う回数は， N を K で割った時の商になります。よって，その操作を行う回数を l とすると，
N – l * K > 0
となるような最大の n を求めてあげると，l + 1 回目の操作では，
(N – l * K) – K < 0
になるので，この値の絶対値を取ることになります。
よって，この２つの数の大小を比較すればいいことになります。
すなわち，出力すべきは

min(N - l * K, abs((N - l * K) - K) 

になります。

解答

n, k = map(int, input().split())

l = n // k

print(min(n - l * k, abs((n - l * k) - k)))