AtCoder ABC 118 C - Monsters Battle Royale (300 点)

問題

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

結論

モンスターの体力すべてについてに最大公約数が答えとなる。

方針

ようやく考察し甲斐のある問題が来たぜ！（震え声）

なんとなく最大公約数じゃね？と思ってサブミットしたらACしちゃった、というのが辛いところ。
実装もシンプルなので、他の人の回答を見てもあまり参考にならないのも難しいところです。

「その時に最も体力が小さいモンスターが殴り続ければ、最後に生き残るモンスターの体力が最小化される」
という仮説を立てます。なんとなく正しい気がします。
この通りに殴り続けると、モンスターの体力が減りゆく様からユークリッドの互除法を感じます。
つまり最小公倍数ってことだな！？ってなります。なりました。

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    cin >> N;
    int A[N];
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    
    int res = A[0];
    for (int i = 1; i < N; ++i) {
        res = __gcd(res, A[i]); // i番目までのモンスターの体力の最大公約数
    }
    
    cout << res << endl;
    
    return 0;
}