Rezolvare PBinfo #4086

Se dă un șir a1, a2, …, an de numere naturale nenule.

Cerința

Să se determine răspunsul pentru una din următoarele cerințe:

• Cel mai mare divizor comun al celor n numere.
• Cel mai mare divizor comun care se poate obține alegând exact n-1 elemente din șir.
• Cel mai mare divizor comun care se poate obține alegând exact n-2 elemente din șir.

Date de intrare

Fișierul de intrare cmmdc.in conține pe prima linie un număr natural T reprezentând cerința cerută (1, 2, sau 3), pe a doua linie se află numărul natural nenul n, iar de pe următoarele n linii se găsesc, câte un număr pe fiecare linie, cele n elemente ale șirului.

Date de ieșire

În fișierul de ieșire cmmdc.out se va afișa răspunsul pentru cerința menționată.

Restricții și precizări

• 2 ≤ a[i] ≤ 263 - 1 oricare 1 ≤ i ≤ n (numerele sunt de tip long long)
• Pentru 16 puncte, T=1, 3 ≤ n ≤ 100.000 și a[i] ≤ 50.000.000, pentru 1 ≤ i ≤ n
• Pentru 20 puncte, T=1 și 3 ≤ n ≤ 100.000
• Pentru 21 puncte, T=2 și 3 ≤ n ≤ 3000
• Pentru 21 puncte, T=2 și 3 ≤ n ≤ 100.000
• Pentru 12 puncte, T=3 și 3 ≤ n ≤ 300
• Pentru 10 puncte, T=3 și 3 ≤ n ≤ 2000

Exemplul 1:

cmmdc.in

1
5
48
40
20
16
80

cmmdc.out

4

Explicație

T = 1, deci se cere determinarea celui mai mare divizor comun al celor cinci numere: 48, 40, 20, 16 și 80.

Exemplul 2:

cmmdc.in

2
5
48
40
20
16
80

cmmdc.out

8

Explicație

T = 2, deci se rezolvă cerința 2. Eliminând numărul 20, rămân n - 1 = 4 numere, iar cmmdc(16, 48, 40, 80) = 8, care este și maximul posibil.

Exemplul 3:

cmmdc.in

3
5
48
40
20
16
80

cmmdc.out

20

Explicație

T = 3, deci se rezolvă cerința 3. Eliminând numerele 16 și 48 rămân n - 2 = 3 numere, iar cmmdc(40, 20, 80) = 20, care este și maximul posibil.