View source for 2296 - gcd

== Cerința ==
Se dau două șiruri de câte N numere naturale fiecare. Se cere să se găsească valoarea maximă a celui mai mare divizor comun a două numere A și B, astfel încât A să aparțină primului șir, iar B să aparțină celui de-al doilea șir.

== Date de intrare ==
În fișierul gcdin.txt se va afla pe prima linie un număr reprezentând valoarea lui N. Pe cea de-a doua linie se vor afla N numere separate prin câte un spațiu, reprezentând elementele primului șir. Pe cea de-a treia linie se vor afla N numere separate prin câte un spațiu, reprezentând elementele celui de-al doilea șir.

== Date de ieșire ==
În fișierul gcdout.txt se va afla pe primia linie un număr natural reprezentând valoarea maximă a celui mai mare divizor comun a două numere A și B, astfel încât A să aparțină primului șir, iar B să aparțină celui de-al doilea șir.

== Restricții și precizări ==
* '''N''' &les; 500.000
* Elementele celor două șiruri sunt mai mici sau egale cu 1.000.000

== Exemplul 1 ==
; Intrare
; gcdin.txt
: 5
: 3 1 4 2 8
: 5 2 12 8 3
; Ieșire
: Datele de intrare corespund restricțiilor impuse
; gcdout.txt
: 8

=== Explicație ===
A = 8, B = 8, iar (A,B) = 8 este valoarea maximă a celui mai mare divizor comun a vreunei perechi.

== Exemplul 2 ==
; Intrare
; gcdin.txt
: 500001
: 3 1 4 2 8
: 5 2 12 8 3
; Ieșire
: Datele de intrare NU corespund restricțiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line>
#2296 - GCD

import math


def validare_date(n, sir1, sir2):
    if not 1 <= n <= 500000:
        return False
    if any(not 1 <= x <= 1000000 for x in sir1 + sir2):
        return False
    return True


def gcd_maxim(sir1, sir2):
    gcd_max = 0
    for a in sir1:
        for b in sir2:
            gcd_max = max(gcd_max, math.gcd(a, b))
    return gcd_max


# Citire date de intrare
with open('gcdin.txt', 'r') as f:
    n = int(f.readline())
    sir1 = list(map(int, f.readline().split()))
    sir2 = list(map(int, f.readline().split()))

# Validare date de intrare
if validare_date(n, sir1, sir2):
    print("Datele de intrare corespund restricțiilor impuse")
    # Calcul și afișare rezultat
    rezultat = gcd_maxim(sir1, sir2)
    with open('gcdout.txt', 'w') as f:
        f.write(str(rezultat) + '\n')
else:
    print("Datele de intrare NU corespund restricțiilor impuse")
    exit(0)

</syntaxhighlight>