GCD#137

GCD (Editorial)

It is known that

GC D (a_{1}, a_{2}, ..., a_{i}) = GC D (GC D (a_{1}, a_{2}, ..., a_{i - 1}), a_{i})

GCD (a_1, a_2, ..., a_i) = GCD (GCD (a_1, a_2, ..., a_{i - 1}) , a_i)

Based on this, the greatest common divisor of two, three, ..., $n$ numbers can be computed sequentially. For example, for four numbers, the following equality holds:

GC D (a_{1}, a_{2}, a_{3}, a_{4}) = GC D (GC D (GC D (GC D (0, a_{1}), a_{2}), a_{3}), a_{4})

GCD (a_1, a_2, a_3, a_4) = GCD (GCD (GCD (GCD (0, a_1), a_2), a_3), a_4)

Algorithm implementation

The function gcd computes the greatest common divisor.

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

Read the input data and sequentially compute the GCD for the given $n$ numbers, storing the result in the variable $r es$ .

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

C++

Print the answer.

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

Python implementation

import math

Read the input data.

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

In the variable $r es$ , sequentially compute the GCD of the given $n$ numbers.

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

Print the answer.

print(res)