TopCoder Statistics - Problem Statement

Problem Statement

We want to be able to express a fraction as a sum of two fractions that have small denominators. Specifically, given a fraction a/b, we want to find fractions c/d and e/f such that

a/b = c/d + e/f, where d and f are positive
max(d,f) is as small as possible

Create a class FracSum that contains a method decompose that is given a and b and that returns the smallest value for max(d,f).

Definition

Class:: FracSum
Method:: decompose
Parameters:: int, int
Returns:: int
Method signature:: int decompose(int a, int b)
(be sure your method is public)

Constraints

a and b will each be between 1 and 2,000,000,000, inclusive.

Examples

14

10

Returns: 5

14/10 = 0/1 + 7/5 is one way to keep the denominators less than or equal to 5.
1

60

Returns: 12

1/60 = -2/5 + 5/12
8

90

Returns: 9

8/90 = -4/5 + 8/9
60

1

Returns: 1
1

1073741824

Returns: 1073741824
1

223092870

Returns: 15015
142498471

969414712

Returns: 110261
969402524

1779771171

Returns: 102871
644728254

539745730

Returns: 7913
174887511

537177095

Returns: 36215
1325961320

1943845226

Returns: 156787
1218329540

1495162667

Returns: 116003
972532777

233630565

Returns: 2225053
856160600

1471849252

Returns: 30929
897542310

490867014

Returns: 391441
1646993492

1359718535

Returns: 37891
588799904

1589095588

Returns: 180497
616464741

679443536

Returns: 42593
1869461383

71931701

Returns: 45613
91778096

1167477923

Returns: 578819
1665050039

1468475924

Returns: 1844819
158794194

482001782

Returns: 19717
1083418454

502431000

Returns: 46625
129034600

1481884249

Returns: 1481884249
1289497509

920149074

Returns: 10267
1535577192

701520105

Returns: 19745
1041456051

181370527

Returns: 30133
422157696

582612464

Returns: 11263
1830896331

1838984131

Returns: 1838984131
699172182

648946242

Returns: 3759
870593196

685474996

Returns: 262433
459081709

1100285524

Returns: 315811
438024751

501238221

Returns: 29469
1153604298

952833023

Returns: 1692421
1013903668

1657155039

Returns: 552385013
1320263529

489570217

Returns: 48913
937158743

1225058721

Returns: 9959827
183175223

669628819

Returns: 11349641
1048257511

1557372544

Returns: 29056
760409201

1967864107

Returns: 268211
419953341

247469247

Returns: 27496583
1021875324

462409942

Returns: 15583
601141236

466382842

Returns: 115613
1341484503

1403068057

Returns: 102511
186943562

1264112143

Returns: 65023
962386688

1630142419

Returns: 1630142419
1018782770

1039826683

Returns: 148546669
1074542221

1564742500

Returns: 63125
86051548

1294935030

Returns: 27711
1108461536

1329872031

Returns: 147763559
1871075132

1998323884

Returns: 665221
418029632

914301789

Returns: 304767263
637791154

1005003430

Returns: 100500343
1043525525

1862678107

Returns: 1862678107
814068936

818195136

Returns: 387403
1976056747

52244468

Returns: 768301
22

4

Returns: 2
944169767

927465625

Returns: 296789
21

21

Returns: 1
1

1483509662

Returns: 741754831
1199999858

1799999787

Returns: 3
1000000000

750000001

Returns: 158663

Statistics

Problem Statement for "FracSum"

Problem Statement

Definition

Constraints

Examples