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 ⩽ 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>

1. 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

1. 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()))

1. 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>