D - Zero Remainder Array

問題

https://codeforces.com/contest/1374/problem/D (新しいタブで開く)

問題文

長さ $n$ の数列 $a$ が与えられる。以下の操作を何回か行って、すべての $i$ について $a_i \bmod k = 0$ にしたい。最小の回数は？

$x = 0$ で初期化する。
操作は以下のどちらか。

• $i$ を 1 つ選ぶ。$a_i$ を $a_i + x$ にして、 $x$ を $x + 1$ する。ただし、同じ $i$ を 2 回以上選ぶことはできない。
• $x$ を $x + 1$ する。

制約

• $1 \le t \le 2 \times 10^4$
• $1 \le n \le 2 \times 10^5$
• $1 \le k \le 10^9$
• $1 \le a_i \le 10^9$
• $n$ の総和は $2 \times 10^5$ を超えない。

サンプル

5
4 3
1 2 1 3
10 6
8 7 1 8 3 7 5 10 8 9
5 10
20 100 50 20 100500
10 25
24 24 24 24 24 24 24 24 24 24
8 8
1 2 3 4 5 6 7 8

6
18
0
227
8

考察

まず、$i$ それぞれについて $(k - a_i) \bmod k$ を求めておき、値ごとに $i$ の個数を数えておく。
つまり、「 $\mathrm{cnt}_j = \left( (k - a_i) \bmod k = j \right)$ となる $i$ の個数」を計算しておく。

$\max \mathrm{cnt}_j$ を $m$ とすると、$m$ 回ぐるぐるする必要がある。そのために必要な操作回数は $m \times k$ 。
ただ、最後の $m$ 周目は最後まで回さなくていいので、$j$ 回増やしておいて、 $a_i := a_i + x$ すればいい。

よって、必要回数は $m (k - 1) + j + 1 = m k - (k - j) + 1$

コード

https://codeforces.com/contest/1374/submission/126809140 (新しいタブで開く)

void solve() {
  ll n, k;
  cin >> n >> k;
  map<ll, ll> rem;
  ll maxim = 0, maximI = 0;
  rep(i, n) {
    ll a;
    cin >> a;
    ll remain = (k - (a % k)) % k;
    rem[remain]++;
    if (maxim <= rem[remain] && remain != 0) {
      if (maxim == rem[remain]) {
        maximI = max(maximI, remain);
      }
      else {
        maximI = remain;
      }
      maxim = rem[remain];
    }
  }
  if (rem[0] == n) {
    cout << 0 << endl;
    return;
  }
  ll ans = (maxim * k) - (k - maximI) + 1;
  cout << ans << endl;
  return;
}