НСД#137

НСД (Розбір)

Відомо, що

НСД (a_{1}, a_{2}, ..., a_{i}) = НСД (НСД (a_{1}, a_{2}, ..., a_{i - 1}), a_{i})

НСД (a_1, a_2, ..., a_i) = НСД (НСД (a_1, a_2, ..., a_{i - 1}) , a_i)

На цій основі можна послідовно обчислювати найбільший спільний дільник двох, трьох, ..., $n$ чисел. Наприклад, для чотирьох чисел виконується рівність:

НСД (a_{1}, a_{2}, a_{3}, a_{4}) = НСД (НСД (НСД (НСД (0, a_{1}), a_{2}), a_{3}), a_{4})

НСД (a_1, a_2, a_3, a_4) = НСД (НСД (НСД (НСД (0, a_1), a_2), a_3), a_4)

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

Функція gcd обчислює найбільший спільний дільник.

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

Читаємо вхідні дані і в змінній $r es$ послідовно обчислюємо НОД для заданих $n$ чисел.

res = 0;
scanf("%d", &n); 
while (n--)
{
  scanf("%d", &b);
  res = gcd(res, b);
}

C++

Виводимо відповідь.

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

Python реалізація

import math

Читаємо вхідні дані.

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

У змінній $r es$ послідовно обчислюємо НОД для заданих $n$ чисел

res = 0
for x in lst:
  res = math.gcd(res, x)

Виводимо відповідь.

print(res)