Enumeration of rationals
All submissions for this problem are available.
It is well known that rational numbers form a countable set. Hence the set of rational numbers in the open interval (0,1) also form a countable set.
Here we enumerate the rationals in (0,1) in the following fashion. First, every rational is expressed in the lowest terms : ie, as p/q where p and q are positive integers with no common factor other than one. Then we sort the fractions in the ascending order of p+q. In case of a tie, the smaller fraction comes first.
The first few terms in this enumeration are 1/2, 1/3, 1/4, 2/3, 1/5, 1/6, 2/5...
Given a natural number N, find the numerator and denominator of the Nth term in the enumeration.
The first line of the input contains T (≤1000), the number of test cases. This is followed by T lines, each containing an integer N(≤1011).
For each value of N, output separated by space the numerator and denominator (in lowest terms) of the Nth fraction in the enumeration
Input: 2 3 6 Output: 1 4 1 6
|Time Limit:||0.373461 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, GO, NODEJS, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.