けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 161 C - Replacing Integer (300 点)

これは問題文がいかめしいけど、ちょくだいさんのこのツイートが全てかなと思う!

問題へのリンク

問題概要

整数  N, K が与えられる。 N に対して以下の操作を好きな回数だけ繰り返すことができる。得られる結果の最小値を求めよ。

  •  N を、 |N - K] で置き換える

制約

  •  1 \le N \le 10^{18}
  •  0 \le K \le 10^{18}

考えたこと

問題文がいかめしいけど、実のところ言っていることはシンプルなのだ。だが、それを読み取るためには、いくつかの  N, K に対して試してみるのがいいと思う。それをしていくうちに、様子をつかむことができる。

 N = 45, K = 8 とかの場合、操作を繰り返すと

45 → 37 → 29 → 21 → 13 → 5 → 3 → 5 → 3 → 5 → 3 → ...

という風になる。 N = 40, K = 8 のときは

40 → 32 → 24 → 16 → 8 → 0 → 8 → 0 → 8 → 0 → ...

という風になる。このように、結局のところ最終的には、

  •  N K で割ったあまり ( N %  K)
  • それを  K から引いた値 ( K -  N %  K)

を繰り返すことになる。よって答えは

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

となる。

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

int main() {
    long long N, K;
    cin >> N >> K;
    cout << min(N % K, K - N % K) << endl;
}