1023 - Cmmdc 3

Cerinţa

Se dă un sir cu n elemente, numere naturale nenule. Folosind metoda Divide et Impera, determinaţi cel mai mare divizor comun al elementelor acestui șir.

Date de intrare

Programul citește de la tastatură numărul n, iar cele n elemente ale șirului.

Date de ieşire

Programul afișează pe ecran numărul X, reprezentând cel mai mare divizor comun al elementelor.

Restricţii şi precizări

• 1 ≤ n ≤ 1000
• elementele șirului vor avea cel mult 9 cifre
• se recomandă folosirea metodei Divide et Impera

Exemplul 1

Date de intrare

7
18 54 24 42 108 60 30

Date de ieșire

6

Exemplul 2

Date de intrare

1001
123

Numerele introduse nu respectă restricțiile.

def verifica_restrictii(n, arr):
    if 1 <= n <= 1000 and all(1 <= num <= 10**9 for num in arr):
        return True
    return False

def cmmd(x, y):
    while y:
        x, y = y, x % y
    return x

def cmmd_divide_et_impera(arr, start, end):
    if start == end:
        return arr[start]
    else:
        mid = (start + end) // 2
        left_cmmd = cmmd_divide_et_impera(arr, start, mid)
        right_cmmd = cmmd_divide_et_impera(arr, mid + 1, end)
        return cmmd(left_cmmd, right_cmmd)

def main():
    n = int(input("Introduceți numărul n: "))
    arr = list(map(int, input("Introduceți cele n elemente separate prin spațiu: ").split()))

    if verifica_restrictii(n, arr):
        rezultat = cmmd_divide_et_impera(arr, 0, n - 1)
        print("Cel mai mare divizor comun:", rezultat)
    else:
        print("Numerele introduse nu respectă restricțiile.")

if __name__ == "__main__":
    main()