| Fişierul intrare/ieşire: | tygyn.in, tygyn.out | Sursă | Tuymaada 2019 |
| Autor | Alexandru Petrescu | Adăugată de |  Alexandru Petrescu •alexpetrescu |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | tygyn.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
