== 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.
One of Marcel's ancestors, called Manchaary, son of Nyurgun and Sahayaana, was one of the servants of Tygyn Darkhan, at the beginning of the 17th century. Tygyn Darkhan, the great leader who unified the Yakutian tribes, seems to have been very passionate about Number Theory.
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:
One day, he assigned some distinct integers from $2$ to $M$ to his $N$ cows. He decided to group the cows, based on their numbers, into as few herds as possible. However, he set the following conditions that should be met for all herds:
* 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.
* Let $x$ be the smallest number assigned to the cows in the herd. Each other number of a cow in the herd is of the form $x * k$, with $k$ integer.
* All divisors of $k$ (apart from $1$) are greater than or equal to any prime divisor of $x$, for all cows in the herd.
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!
However, Tygyn is a bit busy with keeping peace in his territory, so he asked Manchaary to take care of the cows. The task was rather difficult for Manchaary, but the reward was magnificent: he could then marry beautiful 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!
We know the end of the story: Manchaary solved the task and Sardaana became an ancestor of Marcel. However, when Marcel learned about the story, he thought the task can go back to the lands it originated. That is why the participants in Tuymaada 2019 have to solve it!
h2. Date de intrare
h2. Input
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.
Input file $tygyn.in$ contains on the first line the integer numbers $N$ and $M$. The next line contains $N$ numbers with values between $2$ and $M$, representing the distinct numbers assigned to the $N$ cows of Tygyn Darkhan.
h2. Date de iesire
h2. Output
Fisierul de iesire $tygyn.out$ contine numarul minim de turme in care Manchaary poate grupa vacile.
Output file $tygyn.out$ contains the minimal number of herds Manchaary could group the cows into.
h2. Restrictii si precizari
h2. Constraints
* $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.
* For $40$ points, $N ≤ 1.000$
h2. Exemplu
h2. Example
table(example). |_. tygyn.in |_. tygyn.out |
| 5 100
2 3 11 22 12
| 3 |
| 3
|
| 10 20
8 12 20 6 3 7 11 13 19 15
| 9
|
h3. Tutorial
h3. Request
Puteti vedea o solutie in $O(N + M)$ la 'editorial':tygyn/solutie_romana
Contacteaza-l pe autor daca te oferi sa traduci enuntul in limba romana.
== include(page="template/taskfooter" task_id="tygyn") ==
