Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2006-11-11 11:23:40.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:frac.in, frac.outSursăinfo-arena 1.0
AutorFilip Cristian BuruianaAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Frac

Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata.
Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii.

frac

Patratel este mare pasionat de fractii. Intr-o zi el se gandeste sa scrie pe o foaie de hartie, in ordine crescatoare, toate fractiile ireductibile cu numitorul N. Observand insa la timp ca sunt o infinitate de astfel de fractii, el nu se mai oboseste si doreste sa afle doar a P-a fractie din sirul la care s-a gandit.

Cerinta

Sa se determine numaratorul celei de a P-a fractii din sirul construit dupa regulile de mai sus.

Date de Intrare

Prima linie a fisierului frac.in contine doua numere intregi N si P, separate prin cate un spatiu, avand semnificatia descrisa in enunt.

Date de Iesire

Prima linie a fisierului frac.out contine un numar natural care reprezinta numaratorul celei de a P-a fractii din sirul fractiilor ireductibile cu numitorul N.

Restrictii si precizari

o 1 <= N <= 12 000 000 000 ( 12 miliarde )
o 1 <= P <= 10^14
o Se garanteaza ca rezultatul nu depaseste 2^61

Exemplu

frac.in frac.out Explicatie
12 5 13 Fractiile sirului sunt: 1/12, 5/12, 7/12, 11/12, 13/12, 17/12, etc. A 5-a fractie din acest sir este 13/12 si are numaratorul 13.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?