Monsters Battle Royale [AtCoder Beginner Contest 118 C]

https://atcoder.jp/contests/abc118/tasks/abc118_c

前提知識

• GCD、ユークリッドの互除法

解説

https://atcoder.jp/contests/abc118/submissions/4280971

競技プログラミングは時にはエスパー力が求められる。
エスパーをすると、全部のgcdが答えになりそうだと気づくので、それを提出する。
ちなみにエスパーの元は以下のような感じ
　

• 入力例2を見てみると1にすることができる
• これは適当な数だと結構1にできそうな感じがある
• 2,10,8,40で2が帰ってくるが、他が2が他の約数だから、引き算で0にできる
• ん？約数？

　
もう少し踏み込んだ説明をすると、最大公約数を求めるユークリッドの互除法で
引き算をする方法がある。
具体的にはa＞bのとき、gcd(a,b) = gcd(a - b, b)である。
これが問題文にある操作になる。
よって、全てのgcdを取ると、答えになる。

int N, A[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
 
    int ans = 0;
    rep(i, 0, N) ans = gcd(ans, A[i]);
    cout << ans << endl;
}