Fişierul intrare/ieşire:tygyn.in, tygyn.outSursăTuymaada 2019
AutorAlexandru PetrescuAdăugată dealexpetrescuPetrescu Alexandru alexpetrescu
Timp execuţie pe test0.7 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Tygyn

Unul dintre stramosii lui Marcel, Manchaary, fiul lui Nyurgun si Sahayaana, a fost unul dintre servitorii lui Tygyn Darkhan, la inceputul secolului al 17-lea. Tygyn Darkhan, liderul maret care a unificat triburile Yakutiene, parea sa fi fost foarte pasionat despre Teoria Numerelor.

Intr-o zi, a atribuit un numar natural distinct de la 2 la M celor N vaci ale sale. S-a gandit sa grupeze vacile, bazandu-se pe numerele de pe ele, intr-un numar minim de turme. Totusi, a stabilit urmatoarele conditii, care trebuie satisfacute pentru toate turmele:

  • Fie x cel mai mic numar atribuit vacilor dintr-o turma. Fiecare vaca din aceeasi turma trebuie sa aiba un numar de forma x * k, unde k este un numar natural.
  • Toti divizorii primi ai lui k (in afara de 1) trebuie sa fie mai mari sau egali cu orice divizor prim al lui x pentru toate vacile din turma.

Totusi, Tygyn este putin ocupat cu mentinerea pacii pe teritoriul sau, asa ca l-a rugat pe Manchaary sa aiba grija de vaci. Aceasta sarcina parea destul de dificila pentru Manchaary, dar recompensa era minunata: putea sa se casatoreasca cu frumoasa Sardaana!

Stim finalul povestii: Manchaary a rezolvat sarcina si Sardaana a devenit unul dintre stramosii lui Marcel. Totusi, atunci cand Marcel a aflat despre poveste, s-a gandit ca problema poate sa se intoarca la taramurile de provenienta. De aceea, participantii de la Tuymaada 2019 trebuie sa o rezolve!

Date de intrare

Fisierul de intrare tygyn.in contine pe prima linie numerele naturale N si M. Urmatoarea linie contine N numere cu valori intre 2 si M, reprezentand numerele distincte atribuite celor N vaci ale lui Tygyn Darkhan.

Date de iesire

Fisierul de iesire tygyn.out contine numarul minim de turme in care Manchaary poate grupa vacile.

Restrictii si precizari

  • 1 ≤ N < M ≤ 1.000.000
  • Pentru 10 puncte, M ≤ 20
  • Pentru 40 de puncte, N ≤ 1.000
  • Evaluarea este diferita fata de cea din timpul concursului oficial.

Exemplu

tygyn.intygyn.out
5 100
2 3 11 22 12
3
10 20
8 12 20 6 3 7 11 13 19 15
9

Tutorial

Puteti vedea o solutie in O(N + M) la editorial

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?