1. Идея

Нужно найти наибольшее число, которое делит все n чисел a_i.

Это и есть наибольший общий делитель массива, то есть НОД всех элементов.

Главная идея очень простая: НОД нескольких чисел можно считать постепенно:

• сначала взять НОД первого и второго числа,
• потом НОД полученного результата и третьего числа,
• потом НОД результата и четвёртого,
• и так далее.

То есть:

• g = gcd(a_1, a_2)
• g = gcd(g, a_3)
• g = gcd(g, a_4)
• ...
• в конце g и будет ответом.

Для вычисления НОД двух чисел используем алгоритм Евклида.

2. Наблюдения

Наблюдение 1

Если число делит все элементы массива, то оно обязательно делит и НОД любых двух из них.

Поэтому можно постепенно сжимать массив в одно число — текущий НОД.

Наблюдение 2

НОД обладает сочетательностью:

• gcd(a, b, c) = gcd(gcd(a, b), c)

Значит, порядок последовательного вычисления корректен.

Наблюдение 3

Алгоритм Евклида для двух чисел работает так:

• пока b != 0, заменяем пару (a, b) на (b, a % b);
• когда b стало равно 0, ответ — это a.

Это быстро работает даже для больших чисел до 10^9.

Наблюдение 4

Если в какой-то момент текущий НОД стал равен 1, дальше он уже не увеличится, потому что НОД всегда только уменьшается или остаётся тем же. В эталонном решении досрочная остановка не используется, но даже без неё программа проходит ограничения.

3. Алгоритм

1. Считываем n.
2. Считываем числа.
3. Берём первое число как начальный текущий НОД g.
4. Для каждого следующего числа x:
   • заменяем g на gcd(g, x).
5. Выводим g.

Как считать gcd(g, x):

• пока x != 0:
  • сохраняем остаток g % x,
  • сдвигаем значения,
  • продолжаем процесс.

4. Почему это работает

Докажем, что после обработки всех чисел переменная g равна НОД всего массива.

Пусть после обработки первых k чисел значение g равно gcd(a_1, a_2, ..., a_k).

Тогда при добавлении следующего числа a_(k+1) мы вычисляем:

• g = gcd(g, a_(k+1))

Но так как старое g уже равно gcd(a_1, ..., a_k), получаем:

• g = gcd(gcd(a_1, ..., a_k), a_(k+1))
• это то же самое, что gcd(a_1, ..., a_k, a_(k+1))

Значит, инвариант сохраняется.

Сначала, до цикла, g = a_1, а это действительно НОД из одного числа.

После обработки всех n чисел получаем:

• g = gcd(a_1, a_2, ..., a_n)

Именно это число по условию и требуется вывести.

Почему алгоритм Евклида правильно считает НОД двух чисел:

• НОД чисел a и b совпадает с НОД чисел b и a % b.
• Поэтому можно многократно заменять пару чисел, пока второе не станет нулём.
• Когда это произошло, первое число и есть НОД.

Следовательно, весь алгоритм корректен.

5. Сложность

Пусть A — максимальное из чисел массива.

• Вычисление НОД двух чисел алгоритмом Евклида работает за O(log A).
• Мы делаем это n - 1 раз.

Итоговая сложность:

• O(n log A)

Память:

• O(1), если не хранить весь массив;
• в приведённом Python-решении массив считывается целиком, поэтому там используется O(n) памяти.

6. Код на C++17

#include <iostream>
#include <vector>
using namespace std;

long long gcd_ll(long long a, long long b) {
    while (b != 0) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main() {
    int n;
    cin >> n;

    long long g, x;
    cin >> g;
    for (int i = 1; i < n; i++) {
        cin >> x;
        g = gcd_ll(g, x);
    }

    cout << g << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

g = a[0]
for i in range(1, n):
    x = a[i]
    while x != 0:
        g, x = x, g % x

print(g)