CF Round #653 D - Zero Remainder Array


Tags:cpcodeforcesdiv3math

問題

https://codeforces.com/contest/1374/problem/D

問題文

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

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

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

制約

  • 1t2×1041 \le t \le 2 \times 10^4
  • 1n2×1051 \le n \le 2 \times 10^5
  • 1k1091 \le k \le 10^9
  • 1ai1091 \le a_i \le 10^9
  • nn の総和は 2×1052 \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

考察

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

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

よって、必要回数は m(k1)+j+1=mk(kj)+1m (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;
}