AtCoderログ：0106 - ABC 161 C

問題

問題文

青木君は任意の整数 $x$ に対し、以下の操作を行うことができます。
・操作: $x$ を $x$ と $K$ の差の絶対値で置き換える。
整数 $N$ の初期値が与えられます。この整数に上記の操作を $0$ 回以上好きな回数行った時にとりうる $N$ の最小値を求めてください。

制約

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

収録されている問題セット

• AtCoder Problems Boot camp for beginners Easy 100 [#013]

回答

回答1 (AC)

入力値 $x$ が $K$ よりも大きいとき、操作の出力は $x-K$ となります。さらにこの値が $x$ よりも大きいとき、2回目の操作の出力は $x-2K$ となります。同様に繰り返すと、出力値が $x \bmod{K}$ になった時点で値は $K$ 以下となります ($x \bmod K$ は $x$ を $K$ で割った余り)。

他方で入力値 $x$ が $K$ 以下のとき、操作の出力は $K-x$ となります。この値は $K$ 以下なので、2回目の操作の出力は $K-(K-x)=x$ となり、もとの値に戻ります。

これらの考察より、求める最小値は $x \bmod K$ と $K-($x \bmod K$)$ の小さい方になることがわかります。コードは以下のようになりました。

abc161c-1.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
  int64_t n, k;
  cin >> n >> k;

  cout << min( n%k, k-n%k ) << endl;
}  

調べたこと

AtCoder の解説 → コンテスト全体の解説

回答1と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0105 - ABC 217 C
• 次の記事 → AtCoderログ：0107 - ABC 132 C