TopCoder Statistics - 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.

Definition

Class:: FracCount
Method:: position
Parameters:: int, int
Returns:: int
Method signature:: int position(int numerator, int denominator)
(be sure your method is public)

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

1

2

Returns: 1

1/2 is at position 1 in the counting order
5

6

Returns: 11

5/6 is at position 11 in the counting order
999

1000

Returns: 304191
777

778

Returns: 184139
12

625

Returns: 118493
1

111

Returns: 3716
1

512

Returns: 79596
2

889

Returns: 239959
2

3

Returns: 3
2

5

Returns: 7
37

75

Returns: 1715
65

72

Returns: 1585
13

15

Returns: 70
81

1000

Returns: 303824
16

19

Returns: 117
1

1000

Returns: 303792
805

816

Returns: 202456
162

421

Returns: 53817
501

670

Returns: 136459
91

116

Returns: 4115
174

341

Returns: 35339
407

504

Returns: 77316
599

790

Returns: 189766
89

915

Returns: 254296
113

275

Returns: 22964
606

947

Returns: 272697
100

281

Returns: 23959
53

445

Returns: 60046
386

493

Returns: 74040
443

511

Returns: 79537
221

499

Returns: 75638
177

466

Returns: 65958
159

299

Returns: 27194
479

806

Returns: 197404
136

211

Returns: 13549
305

313

Returns: 29940
20

441

Returns: 58985
109

452

Returns: 62088
25

67

Returns: 1352
781

801

Returns: 195264
77

393

Returns: 46871
694

921

Returns: 257984
37

54

Returns: 894
104

321

Returns: 31301
2

5

Returns: 7
76

837

Returns: 212648
227

513

Returns: 79995
301

349

Returns: 37162
23

401

Returns: 48700
29

591

Returns: 105969
330

893

Returns: 242355
21

68

Returns: 1403
7

20

Returns: 122
79

206

Returns: 12895
516

583

Returns: 103496
209

419

Returns: 53350
172

855

Returns: 222030
183

634

Returns: 122141
79

251

Returns: 19102
233

927

Returns: 261011
227

642

Returns: 125252
467

755

Returns: 173342
5

16

Returns: 74
262

945

Returns: 271359
283

726

Returns: 160133
11

14

Returns: 62
999

1000

Returns: 304191
998

999

Returns: 303791
101

501

Returns: 76183
419

600

Returns: 109451
119

600

Returns: 109371
1

3

Returns: 2
2

13

Returns: 47

Statistics

Problem Statement for "FracCount"

Problem Statement

Definition

Constraints

Examples