Fişierul intrare/ieşire:	cufar.in, cufar.out	Sursă	OJI 2018, Clasa a 9-a
Autor	Cristian Toncea	Adăugată de	Andrei Constantinescu •Andrei1998
Timp execuţie pe test	0.75 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Cufar

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.

Cerinţă

Deoarece vrăjitoarea nu are timp la dispoziţie vă roagă pe voi să o ajutaţi să rezolve următoarele probleme:

1. Să afle valoarea magică pentru un cartonaş dat;
2. Să afle cifrul cufărului.

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.

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.

Date de ieşire

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

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

Exemplu

Cum se trimit solutii?