C - Monsters Battle Royale

競プロ

はじめに

競技プログラミング、AtCoder Beginner Contest 118
C - Monsters Battle Royale
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

N体のモンスターが居て、
それぞれ 1,2,...,N と番号付けられています。

はじめ、モンスターiの体力はAiです。
以降、体力が1以上のモンスターを生きているモンスターと呼びます。

生きているモンスターが1体になるまで以下を繰り返します。

ランダムに1体の生きているモンスターが
ランダムに別の生きているモンスターに攻撃します。
その結果、
攻撃されたモンスターの体力を
攻撃したモンスターの体力と同じ値だけ減らします。

最後に生き残ったモンスターの最終的な体力の最小値を求めてください。

制約

入力は全て整数である。
2≤N≤10^5
1≤Ai≤10^9

入力

入力は以下の形式で標準入力から与えられる。

N
A1 A2 ... AN

出力

最後に生き残ったモンスターの最終的な体力の最小値を出力せよ。

解き方

こちらの解き方を参考にしています。 goo.gl goo.gl goo.gl
まず、モンスターが二体しかいない場合を考えてみます。
入力を以下とします。

2
48 30


これを問題文の通りに、戦わせてみると以下のような流れになります。

48 30
18 30
18 12
 6 12
 6  6
 0  6


そして、この流れをよく見てみると
ユークリッドの互除法と同じであることに気づきます。

48%30=18
30%18=12
18%12=6
12%6=6
6%6=0


つまり、最大公約数が答えということになります。

三体目以降は
一、二体目で出した最大公約数の体力を持ったモンスターと
次のモンスターがいると考えて
最大公約数を順番に出していきます。

最終的に出てきた最大公約数が答えです。

全体のコード

using System;
using System.Linq;
using System.Collections.Generic;

class Cmondai
{
    static void Main()
    {
        var N = Int32.Parse(Console.ReadLine());
        var A = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
        var ans = A[0];
        for (int i = 1; i < N; ++i)
        {
            //大きい方をaに入れる
            var a = ans < A[i] ? A[i] : ans;
            //小さい方をbに入れる
            var b = a == ans ? A[i] : ans;
            //最大公約数を得る
            ans = GetGcd(a, b);
        }
        Console.WriteLine(ans);
    }
    //最大公約数を出す
    static long GetGcd(long a, long b)
    {
        while (b != 0)
        {
            var r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}