137. НОД

Найти НОД (наибольший общий делитель) n чисел.

Вход. Первая строка содержит количество чисел n (1 < n < 101). Во второй строке через пробел заданы n натуральных чисел, каждое из которых не превышает 30000.

Выход. НОД заданных чисел.

Пример входа	Пример выхода
2 15 25	5

РЕШЕНИЕ

НОД

Анализ алгоритма

Известно, что

НОД (a₁, a₂, …, a_i) = НОД (НОД (a₁, a₂, …, a_{i - 1}) , a_i)

Будем последовательно вычислять наибольший общий делитель двух, трех, …, n чисел. Например, для четырех чисел имеет место равенство:

НОД (a₁, a₂, a₃, a₄) = НОД (НОД (НОД (НОД (0, a₁), a₂), a₃), a₄)

Реализация алгоритма

Функция gcd вычисляет Наибольший Общий Делитель.

int gcd(int a, int b)

{

return (!b) ? a : gcd(b, a % b);

}

Читаем входные данные и последовательно находим НОД заданных n чисел.

res = 0;

scanf("%d", &n);

while (n--)

{

scanf("%d", &b);

res = gcd(res, b);

}

Выводим ответ.

printf("%d\n", res);