FRACTION - Sort fractions

no tags 

You are given a positive integer N. Let us consider set A of fractions x/y where 0 <= x/y <= 1, y <= N and the maximum common divisor of x and y is 1.

For example N = 5. Set A in increasing order consists of elements 0/1; 1/5; 1/4; 1/3; 2/5; 1/2; 3/5; 2/3; 3/4; 4/5; 1/1.

Your task is to find the i-th smallest fraction in set A.


The first line of input contains the number of testcases t (t <= 15). The first line of each testcase contains numbers N and M (N <= 5000, M <= 10000). The next M lines contain one question each.


For each testcase, you should output M lines which are the answers to the M questions.


5 4


hide comments
ashish kumar: 2015-12-30 11:27:09

what should be time complexity ?

numerix: 2014-11-13 21:13:11

Problem has been switched from Pyramid to Cube cluster these days and time limit has been adjusted. It is too strict for slower languages, my former AC Python solution (using the no longer supported psyco module) does not pass anymore.

Update: Thanks a lot to the problemsetter for increasing the time limit to 2.5 s. A well designed algorithm in some slower languages will now be able to pass.

Last edit: 2014-11-25 21:30:24
sarelfeniel: 2014-01-19 03:19:05

Lots of fun and tons of optimisation to be had :D

sumit agarwal: 2013-06-03 13:56:04

the time constraint is very tight!! awesome question to learn how data types can also lead to TLE :)

Divanshu: 2013-03-28 12:39:08

Dont use C++ pair! Caused me 4 TLE's!! :(

Haijun Deng: 2012-12-26 14:07:10

Oh TLE :(

Benjamin Pinaya: 2012-03-06 01:33:09

Really nice one! It need a lot of optimization but it is awesome!

Prakhar Jain: 2011-12-22 06:19:35

Last edit: 2011-12-22 08:59:56
Jay Pandya: 2011-07-15 08:51:39

the time limit is too strict!! after many tles...finally accepted... phewww

Kunal Kapadia: 2011-07-09 12:26:40

WDF!! gettin TLE again n again.... Even after knowing its Farey Sequence

Added by:Lê Đôn Khuê
Time limit:2.5s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:Mr Nguyen Duc Thinh