Fișierul intrare/ieșire | cmmdc.in, cmmdc.out | Sursă | OJI 2022 Clasa a 6-a |
---|---|---|---|
Autor | Dan Pracsiu | Adăugată de | Cristian Frâncu • francu |
Timp de execuție pe test | 1 sec | Limită de memorie | 131072 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Cmmdc (clasa a 6-a)
Se dă un sir a1, a2, ..., an de numere naturale nenule.
Cerințe
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 pe următoarele n linii se găsesc, câte unul pe fiecare linie, cele n elemente ale șirului.
Date de ieșire
În fișierul cmmdc.out se va afișa răspunsul pentru cerința cerută.
Restricții
- 2 ≤ ai ≤ 263 − 1 oricare 1 ≤ i ≤ n (numerele sunt de tip long long)
- Pentru 16 puncte, T=1, 3 ≤ n ≤ 100.000 și ai ≤ 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
Exemplu
cmmdc.in | cmmdc.out | Explicații |
---|---|---|
1 5 48 40 20 16 80 |
4 |
T = 1 deci se cere determinarea celui mai mare divizor comun al celor cinci numere: 48, 40, 20, 16 și 80. Răspunsul este 4. |
2 5 48 40 20 16 80 |
8 |
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. |
3 5 48 40 20 16 80 |
20 |
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. |