Fișierul intrare/ieșire cmmdc.in, cmmdc.out Sursă OJI 2022 Clasa a 6-a
Autor Dan Pracsiu Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 1 sec Limită de memorie 131072 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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:

  1. Cel mai mare divizor comun al celor n numere.
  2. Cel mai mare divizor comun care se poate obține alegând exact n - 1 elemente din șir.
  3. 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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 6 categorii