farey

Secventa Farey

== include(page="template/taskheader" task_id="farey") ==

==Include(page="template/taskheader" task_id="farey")==

Poveste ...

O secventa farey de ordinul $N$ este secventa tuturor fractiilor ireductibile $^P^/{~Q~}$ cu $0 < P < Q &le; N$, aranjate in ordine crescatoare. De exemplu, secventa Farey de ordinul 5 este:
 
p=. $^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~}$.

h2. Cerinta

...

Dandu-se $N$ si un numar $K$, aflati a $K$-ua fractie dintr-o secventa Farey de ordin $N$.

h2. Restrictii

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

h2. Date de intrare

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

h2. Date de iesire

h2. Restrictii si precizari

...

* $1 < N &le; 40 000$
* $40%$ din teste vor avea $K &le; 50 000$
* toate datele de test folosite pentru evaluare vor avea $N &ge; 10 000$

h2. Exemplu

| farey.in | farey.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. farey.in |_. farey.out |
| 5 6 | 3 5 |
 
h3. Sfat prietenesc

== include(page="template/taskfooter" task_id="farey") ==

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.
 
==Include(page="template/taskfooter" task_id="farey")==
 
 

895