Tygyn

tygyn

== include(page="template/taskheader" task_id="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!

Poveste şi cerinţă...

h2. 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.

Fişierul de intrare $tygyn.in$ ...

h2. Date de iesire

h2. Date de ieşire

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

În fişierul de ieşire $tygyn.out$ ...

h2. Restrictii si precizari

h2. Restricţii

* $1 &le; N < M &le; 1.000.000$
* Pentru $10$ puncte, $M &le; 20$
* Pentru $40$ de puncte, $N &le; 1.000$
* Evaluarea este diferita fata de cea din timpul concursului oficial.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. tygyn.in |_. tygyn.out |

| 5 100
2 3 11 22 12
| 3 |
| 10 20
8 12 20 6 3 7 11 13 19 15
| 9
|

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

h3. Tutorial

h3. Explicaţie

Puteti vedea o solutie in $O(N + M)$ la 'editorial':tygyn/solutie_romana

...

== include(page="template/taskfooter" task_id="tygyn") ==