Vrăjitoarea cea bună are un cufăr în care este închisă piatra magică de către piticii lăzii cu ajutorul unui cifru digital. Piticii i-au dat vrăjitoarei o cutie în care sunt n cartonaşe. Pe fiecare cartonaş este scris un număr natural pe care vrăjitoarea îl va folosi să deschidă lada. Valorile scrise pe cartonaşe sunt distincte între ele.
Pentru a afla cifrul trebuie să procedeze astfel: extrage fiecare cartonaş din cutie şi apoi determină valoarea magică asociată numărului natural scris pe cartonaş. Pentru fiecare cartonaş valoarea magică este dată de al k-lea divizor prim al numărului înscris pe acesta. Vrăjitoarea trebuie să adune valorile magice obţinute pentru cele n cartonaşe şi apoi să introducă în ordine cifrele valorii obţinute, pentru a descuia lada.
Pentru a afla cifrul trebuie să procedeze astfel: extrage fiecare cartonaş din cutie şi apoi determină valoarea magică asociată numărului natural scris pe cartonaş. Pentru fiecare cartonaş valoarea magică este dată de al $k$-lea divizor prim al numărului înscris pe acesta. Vrăjitoarea trebuie să adune valorile magice obţinute pentru cele n cartonaşe şi apoi să introducă în ordine cifrele valorii obţinute, pentru a descuia lada.
h2. Cerinţă
h2. Date de intrare
Fişierul de intrare este cufar.in.
Pe prima linie a fişierului de intrare se găsesc o valoare p care poate fi doar 1 sau 2 şi numărul n de cartonaşe despărţite prin câte un spaţiu.
Fişierul de intrare este $cufar.in$.
Pe prima linie a fişierului de intrare se găsesc o valoare $p$ care poate fi doar $1$ sau $2$ şi numărul $n$ de cartonaşe despărţite prin câte un spaţiu.
Dacă p este 1 pe linia a doua a fişierului de intrare se găsesc două valori reprezentând numărul de pe cartonaşul dat şi valoarea k, separate printr-un spaţiu, cu semnificaţia de mai sus.
Dacă $p$ este $1$ pe linia a doua a fişierului de intrare se găsesc două valori reprezentând numărul de pe cartonaşul dat şi valoarea $k$, separate printr-un spaţiu, cu semnificaţia de mai sus.
Dacă p este 2 pe următoarele n linii ale fişierului de intrare se găsesc câte două valori, separate prin câte un spaţiu, reprezentând numărul de pe cartonaş şi valoarea lui k pentru fiecare din cele n cartonaşe.
Dacă $p$ este $2$ pe următoarele $n$ linii ale fişierului de intrare se găsesc câte două valori, separate prin câte un spaţiu, reprezentând numărul de pe cartonaş şi valoarea lui $k$ pentru fiecare din cele $n$ cartonaşe.
h2. Date de ieşire
Fişierul de ieşire este cufar.out.
Fişierul de ieşire este $cufar.out$.
Dacă valoarea lui p este 1, atunci se va rezolva doar cerinţa 1 şi fişierul de ieşire va conţine pe prima
linie valoarea magică asociată cartonaşului dat.
Dacă valoarea lui $p$ este $1$, atunci se va rezolva doar cerinţa $1$ şi fişierul de ieşire va conţine pe prima linie valoarea magică asociată cartonaşului dat.
Dacă valoarea lui p este 2, atunci se va rezolva doar cerinţa 2 şi fişierul de ieşire va conţine pe prima
linie cifrul necesar deschiderii cufărului.
Dacă valoarea lui $p$ este $2$, atunci se va rezolva doar cerinţa $2$ şi fişierul de ieşire va conţine pe prima linie cifrul necesar deschiderii cufărului.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ n < 1 000 000$
* $2 ≤ valoarea înscrisă pe un cartonaş ≤ 1 000 000$
* Se garantează că pentru fiecare pereche $(număr, k)$, număr are cel puţin $k$ divizori primi.
* Pentru rezolvarea corectă a cerinţei $1$ se acordă $18$ puncte
* Pentru rezolvarea corectă a cerinţei $2$ se acordă $72$ de puncte
* Pentru rezultate corecte la cerinţa a doua respectând restricţiile problemei şi $n ≤ 1 000$ se acordă $18$ puncte
* Pentru rezultate corecte la cerinţa a doua respectând restricţiile problemei şi $n ≤ 500 000$ se acordă $43$ de puncte
* Conform regulamentului OJI, se vor acorda $10$ puncte din oficiu (pentru rezolvarea exemplelor).
h2. Exemplu
table(example). |_. cufar.in |_. cufar.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
table(example). |_. cufar.in |_. cufar.out |_. Explicaţie |
| 1 1
30 3
| 5
| $p = 1$, $n = 1$
Se rezolvă doar **prima** cerinţă.
Al $3$-lea divizor prim al numărului $30$ este 5.|
| 2 5
30 3
64 1
105 2
1001 3
5474 4
| 48
| $p = 2$, $n = 5$
Se rezolvă doar **a doua** cerinţă.
Al $3$-lea divizor prim al numărului $30$ este $5$.
Primul divizor prim al numărului $64$ este $2$.
Al 2-lea divizor prim al numărului $105$ este $5$.
Al 3-lea divizor prim al numărului $1001$ este $13$.
Al 4-lea divizor prim al numărului $5474$ este $23$.
Suma căutată va fi $S = 5 + 2 + 5 + 13 + 23$, de unde rezultă cifrul $48$.|
== include(page="template/taskfooter" task_id="cufar") ==
