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

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

AtCoder ABC 103 C - Modulo Summation (300 点)

 a_1, a_2, \dots, a_N が互いに素でない場合とか一瞬だけ怖くなるけど、信じて提出する!!!!!!!

問題へのリンク

問題概要 (ABC 103 C)

 N 個の整数  a_1, a_2, \dots, a_N が与えられる。
様々な非負整数  M に対して

  •  M a_1 で割ったあまり
  •  M a_2 で割ったあまり
  •  \dots
  •  M a_N で割ったあまり

の総和を考えたとき、その最大値を求めよ。

制約

  •  2 \le N \le 3000

解法

  •  M a_1 で割ったあまりが  a_1-1
  •  M a_2 で割ったあまりが  a_2-1
  •  \dots
  •  M a_N で割ったあまりが  a_N-1

という風にできるならそのときが明らかに最大である。実はそれができる 。つまり答えは

 \sum_{i = 1}^{N} a_i - N

である。

上記のようにできることをちゃんと詰める。


 M a で割ったあまりが  a-1

 M+1 a で割り切れる


であることに注目する。したがって、条件は

  •  M + 1 a_1 で割り切れる
  •  M + 1 a_2 で割り切れる
  •  \dots
  •  M + 1 a_N で割り切れる

と言い換えられるので、最小公倍数を LCM で表すことにして

  •  M = {\rm LCM}(a_1, a_2, \dots, a_N) - 1

が条件を満たす。あるいは単に

  •  M = a_1 a_2 \dots a_N - 1

でもよい。

#include <iostream>
using namespace std;

int main() {
    int N; cin >> N;
    long long sum = 0;
    for (int i = 0; i < N; ++i) {
        long long a; cin >> a;
        sum += a;
    }
    cout << sum - N << endl;
}