FracCount
SRM 247 · 2005-06-18 · by dgoodman
SRM 247 · 2005-06-18 · by dgoodman · Brute Force, Simple Math
Problem Statement
Problem Statement
It is possible to assign a unique integer value to each irreducible fraction
between 0 and 1. (This shows that there are a countable infinity of fractions.)
The usual way to number them is shown below
1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5 1/6 5/6 1/7 ...Notice that 2/4, for example, does not get listed because it reduces to 1/2. Given an irreducible fraction we want to find where it appears in the above counting order, where 1/2 is counted as 1, 1/3 as 2, etc.
Create a class FracCount that contains a method position that is given the numerator and denominator of an irreducible fraction between 0 and 1 and that returns its position in the counting order.
Constraints
- numerator will be between 1 and denominator - 1 inclusive.
- denominator will be between 2 and 1,000 inclusive.
- The greatest common divisor of numerator and denominator will be 1.
Examples
0)
1 2 Returns: 1
1/2 is at position 1 in the counting order
1)
5 6 Returns: 11
5/6 is at position 11 in the counting order
2)
999 1000 Returns: 304191
3)
777 778 Returns: 184139
4)
12 625 Returns: 118493
Submissions are judged against all 73 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FracCount with a public method int position(int numerator, int denominator) · 73 test cases · 2 s / 256 MB per case