Fişierul intrare/ieşire:gcd2.in, gcd2.outSursăad-hoc
AutorAdăugată deCCEX2015CCEX2015 CCEX2015
Timp execuţie pe test0.25 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Gcd2

Fie V o mulţime de N numere naturale. Se cere să se găsească cardinalul minim al unei submulţimi W a lui V cu proprietatea că cel mai mare divizor comun al elementelor din W este egal cu 1. În cazul în care o asemenea submulţime nu există, se va afişa -1.

Date de intrare

Fişierul de intrare gcd2.in va conţine pe prima sa linie un număr natural N, reprezentând cardinalul mulţimii V. Urmează pe a doua linie N numere naturale, reprezentând elementele mulţimii V.

Date de ieşire

În fişierul de ieşire gcd2.out va conţine pe unica sa linie numărul MIN, cardinalul minim al unei submulţimi a lui V care are cel mai mare divizor comun al elementelor egal cu 1.

Restricţii

  • 1 ≤ N ≤ 500
  • 1 ≤ V[i] ≤ 109

Exemplu

gcd2.ingcd2.out
4
15 30 10 6
3

Explicaţie

Putem alege submulţimea {6, 10, 15}.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?