The Farey sequence of order N is the sequence of all irreducible fractions p/q with 0< p< q ≤ N, arranged in increasing order. For instance, the Farey sequence of order 5 is:
1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5
We number all fractions in the sequence starting at 1. For instance, the 6th fraction in the sequence of order 5 is 3/5.
There are multiple test cases.
For each test case, given a number N(1<=N<=1,000,000) and a number K in a line, determine the Kth fraction in the sequence of order N.
N=K=0 terminates the input.
The output file should contain a single line, consisting of two integers P and Q separated by a space. The fraction P/Q must be the Kth fraction in the Farey sequence of order N. The fraction must be irreducible, i.e. the greatest common divisor of P and Q must be 1.
You may assume such fraction exists for all test cases.
5 6 1000000 1 1000000 303963552391 0 0
3 5 1 1000000 999999 1000000
請盡量降低乘法和除法的計算量。
Migrated from old NTUJ.
Balkan Olympiad in Informatics 2003, farey
| No. | Testdata Range | Score |
|---|