Fişierul intrare/ieşire:farey.in, farey.outSursăBOI 2003
AutorMihai PatrascuAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.infarey.out
5 63 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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content