== include(page="template/taskheader" task_id="cufar") ==
Poveste şi cerinţă...
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.
h2. Cerinţă
Deoarece vrăjitoarea nu are timp la dispoziţie vă roagă pe voi să o ajutaţi să rezolve următoarele probleme:
# Să afle valoarea magică pentru un cartonaş dat;
# Să afle cifrul cufărului.
h2. Date de intrare
Fişierul de intrare $cufar.in$ ...
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 $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
În fişierul de ieşire $cufar.out$ ...
Fişierul de ieşire este $cufar.out$.
h2. Restricţii
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.
h2. Exemplu
h2. Restricţii
table(example). |_. cufar.in |_. cufar.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
* $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).
h3. Explicaţie
h2. Exemplu
...
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") ==
