FRACTION - Sort fractions
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.
Input
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.
Output
For each testcase, you should output M lines which are the answers to the M questions.
Example
Input: 1 5 4 1 3 5 8 Output: 0/1 1/4 2/5 2/3
hide comments
lokesh_2052:
2021-02-25 12:51:06
https://en.wikipedia.org/wiki/Farey_sequence#Next_term Last edit: 2021-02-26 06:29:48 |
|
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.
|
|
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!!...an 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! |
|
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ê |
Date: | 2005-07-12 |
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 |