Fişierul intrare/ieşire: | frac.in, frac.out | Sursă | info-arena 1.0 |
Autor | Filip Cristian Buruiana | Adăugată de | |
Timp execuţie pe test | 0.025 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
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
- 1 ≤ N ≤ 12 000 000 000 ( 12 miliarde )
- 1 ≤ P ≤ 1014
- Se garanteaza ca rezultatul nu depaseste 261
Exemplu
frac.in | frac.out |
---|---|
12 5 | 13 |
Explicatie
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.