TopCoder problem "NthFraction" used in TCCC05 Round 2 (Division I Level Two)



Problem Statement

    Given an int, bound, consider the infinite set of all reduced fractions whose numerator is a positive integer and whose denominator is a positive integer less than or equal to bound. Now, find the Nth smallest (indexed from 1) fraction and return it as a String in the form "a/b", with no leading zeros in either integer. See example 0 for further clarifications.
 

Definition

    
Class:NthFraction
Method:getFraction
Parameters:int, int
Returns:String
Method signature:String getFraction(int N, int bound)
(be sure your method is public)
    
 

Notes

-A reduced fraction is one of the form a/b for which there is no integer g > 1 such that both a and b are divisible by g.
 

Constraints

-N will be between 1 and 2,000,000,000, inclusive.
-bound will be between 1 and 1000, inclusive.
 

Examples

0)
    
5
3
Returns: "4/3"
The ordered set of fractions is

{1/3, 1/2, 2/3, 1/1, 4/3, 3/2, 5/3, ...}
1)
    
1000
100
Returns: "18/55"
2)
    
1
1000
Returns: "1/1000"
3)
    
1000000
1
Returns: "1000000/1"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3436

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6529&pm=3436

Writer:

lars2520

Testers:

PabloGilberto , Yarin , vorthys

Problem categories:

Advanced Math, Sorting