問題
思考の過程
・入力例1 をベースに考える。なぜ m == 11 の時 最大なのか？
・試しに m を大きくして考える。
m == 13 の時、3。m == 19 の時、5。。確かに 11 が最大なぜ？
・気持ちを切り替えて ai の要素、一つに着目した。
入力例 1 にある a1 = 3 を使用。
m' mod 3 として m' を振る。
| m' | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| m' mod 3 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 |
上記に a2 = 4, a3 = 6 を追加してみる。
| m' | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| m' mod 3 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 |
| m' mod 4 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 |
| m' mod 6 | 1 | 2 | 3 | 4 | 5 | 0 | 1 | 2 | 3 | 4 | 5 | 0 | 1 | 2 | 3 |
入力 ai(1<= i <= N) の最小公倍数-1 とできれば mod は最大となる事に気が付く
・以下のコードで WA
abc103.cpp
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
int main() {
int N; cin >> N;
vector<int>a(N, 0);
long long num = 0;
for (int i = 0; i < N; i++)
cin >> a[i];
num = lcm(a[0], a[1]);
if (N > 2) {
for (int i = 2; i <N; i++)
num = lcm(num, a[i]);
}
long long ans = 0;
for (int i = 0; i < N; i++) {
ans += (num - 1) % a[i];
}
cout << ans;
//while (1) {}
return 0;
}
・以下の記事を確認、なるほどオーバフローか。。
・念のため以下のようなコードでオーバーフロー対策を組み込んだが WA。
abc103.cpp
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
/*オーバーフロー対策*/
long long LCM(long long a, long long b) {
long long A = max(a, b);
long long B = min(a, b);
long long C = (A / gcd(a, b)) * B;
return C;
}
int main() {
int N; cin >> N;
vector<long long>a(N, 0);
long long num = 0;
for (int i = 0; i < N; i++)
cin >> a[i];
num = LCM(a[0], a[1]);
//cout << num << "\n";
for (int i = 2; i <N; i++)
num = LCM(num, a[i]);
long long ans = 0;
for (int i = 0; i < N; i++) {
ans += (num - 1) % a[i];
}
cout << ans;
//while (1) {}
return 0;
}
・m は相当でかくなるケースが予想されるが、実際に目で見て確かめたかった。
テストケースで掲載されているデータを抜き取って検証してみた。
long long を使ってコレなので、lcm , gcd は諦めた方が良さそうだ。
test_case_result.cpp
//input
//10
//43285 7144 60474 3631 15359 6872 32419 91954 79669 11943
//output
//9350128245480
//33950315659337880
//4934064147903053672
//-4390033904473767432
//-3878620465875660568
//-2658199015010463064
//-7435360682929294136
//2113334613221613176
なるほど、自分が悪かったです、すいません。
・最小公倍数-1 の場合、各要素は ai-1 となることが分かっている。
ai-1 を足し合わせれば余りは最大になる。
| m' | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| m' mod 3 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 |
| m' mod 4 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 |
| m' mod 6 | 1 | 2 | 3 | 4 | 5 | 0 | 1 | 2 | 3 | 4 | 5 | 0 | 1 | 2 | 3 |
AC のコード
abc103.cpp
#include <iostream>
using namespace std;
int main() {
int N,a; cin >> N;
long long ans = 0;
for (int i = 0; i < N; i++){
cin >> a;
ans += a - 1;
}
cout << ans;
//while (1) {}
return 0;
}
・解説でも m を求めずに答えを出すように推奨している。
・python なら gcd を使っても AC は取れる
abc103.py
N = int(input())
A = list(map(int,input().split()))
from math import gcd
x = (A[0]*A[0+1])//gcd(A[0],A[0+1])
for i in range(2,N):
x = (x*A[i])//gcd(x,A[i])
#print(x)
ans = 0
for i in range(N):
ans += (x-1)%A[i]
print(ans)
自力で lcm に辿り着いたときは勝利を確信した、恥ずかしながら(笑)
まぁ、こんなこともあるさぁ。
だから C++ AC 回答をひっくり返しても lcm,gcd を使った例が無かったのね。。。ort