ABC103 : C - Modulo Summation にチャレンジ

# [問題](https://atcoder.jp/contests/abc103/tasks/abc103_c)
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/a88ab893-f388-ef00-face-a8683abe1330.png)

# 思考の過程
・入力例1 をベースに考える。なぜ _m_ == 11 の時 最大なのか？

・試しに _m_ を大きくして考える。
&emsp;_m_ == 13 の時、3。_m_ == 19 の時、5。。確かに 11 が最大なぜ？

・気持ちを切り替えて _ai_ の要素、一つに着目した。
&emsp;入力例 1 にある a1 = 3 を使用。 
&emsp;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|

&emsp;上記に a2 = 4, a3 = 6 を追加してみる。

|m'|1|2|3|4|5|6|7|8|9|10|<font color="Red">11|12|13|14|15|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|m' mod 3|1|2|0|1|2|0|1|2|0|1|<font color="Red">**2**|0|1|2|0|
|m' mod 4|1|2|3|0|1|2|3|0|1|2|<font color="Red">**3**|0|1|2|3|
|m' mod 6|1|2|3|4|5|0|1|2|3|4|<font color="Red">**5**|0|1|2|3|

&emsp;入力 _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;
}
```

・以下の記事を確認、なるほどオーバフローか。。

https://cpprefjp.github.io/reference/numeric/lcm.html

https://qiita.com/happyisland44/items/8c06efe2b84e9453447a

・念のため以下のようなコードでオーバーフロー対策を組み込んだが 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 は相当でかくなるケースが予想されるが、実際に目で見て確かめたかった。
&emsp;テストケースで掲載されているデータを抜き取って検証してみた。
&emsp;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
```

&emsp;なるほど、自分が悪かったです、すいません。

・最小公倍数-1 の場合、各要素は ai-1 となることが分かっている。  
&emsp;ai-1 を足し合わせれば余りは最大になる。

|m'|1|2|3|4|5|6|7|8|9|10|<font color="Red">11|12|13|14|15|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|m' mod 3|1|2|0|1|2|0|1|2|0|1|<font color="Red">**2**|0|1|2|0|
|m' mod 4|1|2|3|0|1|2|3|0|1|2|<font color="Red">**3**|0|1|2|3|
|m' mod 6|1|2|3|4|5|0|1|2|3|4|<font color="Red">**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