1. Идея

Нужно найти НОД всех чисел массива.

Главная идея очень простая: будем идти слева направо и поддерживать текущий ответ ans — НОД всех уже просмотренных элементов.

Сначала можно взять ans = 0, а затем для каждого числа x делать:

• ans = gcd(ans, x)

Почему удобно начинать с нуля? Потому что gcd(0, x) = x, значит первый элемент просто станет текущим НОД.
Если все элементы равны нулю, то ответ так и останется 0, что совпадает с условием.

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

Наблюдение 1. НОД можно считать последовательно

Операция НОД ассоциативна:

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

Значит не нужно хранить какие-то сложные структуры. Достаточно постепенно объединять числа.

Например, для массива 6 12 18 24:

• сначала gcd(0, 6) = 6
• потом gcd(6, 12) = 6
• потом gcd(6, 18) = 6
• потом gcd(6, 24) = 6

Ответ: 6.

Наблюдение 2. НОД двух чисел находится алгоритмом Евклида

Для двух чисел a и b:

• пока b != 0, заменяем
  • a = b
  • b = a % b
• когда b стало равно 0, ответом будет a

Это классический алгоритм Евклида.

Наблюдение 3. Нули обрабатываются корректно

В задаче есть неотрицательные числа, среди них могут быть нули.

Полезные факты:

• gcd(0, x) = x
• gcd(0, 0) = 0

Поэтому специальная обработка нулей не нужна.

3. Алгоритм

1. Считываем n.
2. Считываем n чисел.
3. Заводим переменную ans = 0.
4. Для каждого числа x обновляем:
   • ans = gcd(ans, x)
5. Выводим ans.

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

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

Будем рассуждать по шагам.

После обработки первого элемента a_1:

• ans = gcd(0, a_1) = a_1

То есть ans равен НОД первого элемента.

Предположим, что после обработки первых k элементов переменная ans равна:

gcd(a_1, a_2, ..., a_k)

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

ans = gcd(ans, a_(k+1))

Подставим предположение:

ans = gcd(gcd(a_1, ..., a_k), a_(k+1))

Из ассоциативности НОД получаем:

ans = gcd(a_1, a_2, ..., a_k, a_(k+1))

Значит после этого шага ans снова равен НОД всех уже обработанных элементов.

Следовательно, после обработки всего массива в ans будет:

gcd(a_1, a_2, ..., a_n)

Именно это и требуется найти.

5. Сложность

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

• Один вызов gcd(a, b) работает за O(log A).
• Мы вызываем его n раз.

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

• O(n log A)

Память:

• O(1), если не хранить весь массив и обрабатывать числа по мере чтения.

6. Код на C++17

#include <iostream>
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 ans = 0;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        ans = gcd_ll(ans, x);
    }

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

7. Код на Python 3

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

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

ans = 0
for x in a:
    ans = gcd(ans, x)

print(ans)