が互いに素でない場合とか一瞬だけ怖くなるけど、信じて提出する!!!!!!!
問題概要
個の整数 が与えられる。
様々な非負整数 に対して
- を で割ったあまり
- を で割ったあまり
- を で割ったあまり
の総和を考えたとき、その最大値を求めよ。
制約
解法
- を で割ったあまりが
- を で割ったあまりが
- を で割ったあまりが
という風にできるならそのときが明らかに最大である。実はそれができる 。つまり答えは
である。
上記のようにできることをちゃんと詰める。
を で割ったあまりが
⇔
は で割り切れる
であることに注目する。したがって、条件は
- が で割り切れる
- が で割り切れる
- が で割り切れる
と言い換えられるので、最小公倍数を LCM で表すことにして
が条件を満たす。あるいは単に
でもよい。
#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; }