教育的！！！

問題概要

$N$ 個の正の整数 $A_1, A_2, \dots, A_N$ が与えられる。今、以下の操作を好きな回数だけ行う。

$N$ 個から 2 つの正の整数 $a, b$ ( $a \ge b$ ) を選んで、 $a$ を $a-b$ で置き換える

この操作を行うと、最終的には $N-1$ 個の $0$ と 1 個の正の整数が残る。残る整数の最小値を求めよ。

制約

$2 \le N \le 10^{5}$

考えたこと

整数の足し引きを繰り返す局面では、最大公約数に関する性質を疑うとよさそう。今回、あまり深く考えずに「最大公約数だ！」という直感を信じて突き進むので良さそう。一応、ちゃんと証明してみる。

さて、整数の足し引きから想起される最大公約数にまつわる性質として主なものが以下の 2 つ。

ユークリッドの互除法

$a, b$ に対して、 $a$ を $a$ % $b$ で置き換えることを繰り返すアルゴリズムだが、

${\rm GCD}(a, b) = {\rm GCD}(a - b, b)$

という性質を利用していると言える。整数の足し引きに関する性質となっている。

ベズーの定理

最近の AtCoder でたまに見るもの。整数 $a, b$ に対して

$ax + by$ 　( $x, y$ は整数)

という形で書ける整数は、 $g = {\rm GCD}(a, b)$ の倍数に限られる (逆に $g$ の倍数はすべて作れる) というもの

元の問題に戻り...

今回の問題で、最後に残る整数は結局 $A_1, A_2, \dots, A_N$ の線形結合和

$A_1 x_1 + A_2 x_2 + \dots + A_N x_N$

で表されるものになることがわかる。よって、作られる整数は $g = {\rm GCD}(A_1, A_2, \dots, A_N)$ の倍数に限られることがわかる。

逆に、今回 $g$ はユークリッドの互除法を繰り返せば作れる。問題の操作はまさに「選んだ 2 整数に対するユークリッドの互除法の一部」になっている。

よって、まず $A_1, A_2$ によって ${\rm GCD}(A_1, A_2)$ を作ることができて、次にそれと $A_3$ によって ${\rm GCD}(A_1, A_2, A_3)$ ができて...を繰り返すと最後に残るのは、 $g = {\rm GCD}(A_1, A_2, \dots, A_N)$ になる。

#include <iostream>
#include <vector>
using namespace std;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }

int main() {
    int N; cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    long long res = A[0];
    for (int i = 0; i < N; ++i) {
        res = GCD(res, A[i]);
    }
    cout << res << endl;
}