EBOB#137

EBOB (Həll təhlili)

Məlumdur ki

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

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

Bu əsasa görə iki, üç, ..., $n$ ədədlərin ən böyük ortaq bölənini ardıcıl hesablamaq mümkündür. Məsələn, dörd ədəd üçün bu bərabərlik doğrudur:

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

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

Alqoritmin reallaşdırılması

gcd funksiyası ən böyük ortaq böləni hesablayır.

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

Giriş məlumatlarını oxuyuruq və $r es$ dəyişənində verilmiş $n$ ədədlər üçün ardıcıl olaraq NOD hesablayırıq.

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

C++

Cavabı çıxırıq.

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

Python reallaşdırılması

import math

Giriş məlumatlarını oxuyuruq.

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

$r es$ dəyişənində verilmiş $n$ ədədlər üçün ardıcıl olaraq NOD hesablayırıq

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

Cavabı çıxırıq.

print(res)