Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | farey.in, farey.out | Sursă | BOI 2003 |
| Autor | Mihai Patrascu | Adăugată de | |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |  5/5 |
Vezi solutiile trimise | Statistici
Secventa Farey
O secventa farey de ordinul N este secventa tuturor fractiilor ireductibile p/q cu 0 < p < q ≤ N, aranjate in ordine crescatoare. De exemplu, secventa Farey de ordinul 5 este:
1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5
Vom numerota fractiile din secventa incepand cu 1. De exemplu, a 6-a fractie din secventa Farey de ordin 5 este 3/5.
Cerinta
Dandu-se N si un numar K, aflati a K-ua fractie dintr-o secventa Farey de ordin N.
Date de Intrare
Fisierul de intrare farey.in contine o singura linie cu numerele N si K separate prin spatiu. K va fi mereu un index valid, adica va fi cel putin 1 si nu va fi mai mare decat numarul de fractii din secventa Farey de ordin N.
Date de Iesire
Fisierul de iesire farey.out va contine o singura linie cu doua numere intregi P si Q separate prin spatiu. Fractia P/Q trebuie sa fie a K-ua fractie din secventa Farey de ordin N. Fractia trebuie sa fie ireductibila, adica cel mai mare divizor comun dintre P si Q trebuie sa fie 1.
Restrictii si precizari
- 1 < N ≤ 40 000
- 40% din teste vor avea K ≤ 50 000
- toate datele de test folosite pentru evaluare vor avea N ≥ 10 000
Exemplu
| farey.in | farey.out |
|---|---|
| 5 6 | 3 5 |
Sfat prietenesc
Aceasta nu este o problema de matematica; pentru a o rezolva sunt necesare doar cunostiinte matematice elementare. Trebuie in schimb sa gasiti un algoritm performant pentru a o rezolva.
