Statistics

Problem Statement for "FractionInDifferentBases"

Problem Statement

This problem statement contains superscripts and/or subscripts. It may not display properly outside the applet.


It is well-known that when writing a fraction as a rational number, we will either get a finite expansion or an infinite (but periodic) expansion. For example, 1/8 written in base 10 is 0.125, and 1/9 written in base 10 is 0.1111...

The same fraction can have a finite expansion in some bases and an infinite one in other bases. For example, 1/9 had an infinite expansion in base 10, but 1/9 written in base 3 is 0.01 and 1/9 in base 9 is 0.1.

Little Arthur loves numbers and especially the ones that are infinitely long. For a given fraction P/Q he would like to find all integer bases between A and B, inclusive, such that the fraction has an infinite expansion.

Given ints P, Q, A, and B return the number of such bases.

Definition

Class:
FractionInDifferentBases
Method:
getNumberOfGoodBases
Parameters:
long, long, long, long
Returns:
long
Method signature:
long getNumberOfGoodBases(long P, long Q, long A, long B)
(be sure your method is public)

Notes

  • Number X written in an integer base b is a sequence of digits (containing a single separator point, if the number is not an integer) dndn-1..d1d0.d-1..d-m where each di has an integer value between 0 and b-1, inclusive.
  • The notation effectively means that X = dn*bn + dn-1*bn-1 + .. + d1*b1 + d0*b0 + d-1*b-1 + .. + d-m*b-m.
  • Note that X having an infinite expansion in base b means that number X cannot be expressed as a sum with finitely many powers of b.

Constraints

  • P will be between 0 and 1000000000000 (1012), inclusive.
  • Q will be between 1 and 1000000000000 (1012), inclusive.
  • A and B will each be between 2 and 1000000000000000000 (1018), inclusive.
  • A will be less than or equal to B.

Examples

  1. 1

    2

    10

    10

    Returns: 0

    1/2 in base 10 is 0.5, thus, there is no base in the interval where 1/2 has an infinite expansion.

  2. 1

    9

    9

    10

    Returns: 1

    From the problem statement we see that 1/9 has an infinite expansion in base 10, but not in base 9.

  3. 5

    6

    2

    10

    Returns: 8

  4. 2662

    540

    2

    662

    Returns: 639

  5. 650720

    7032600

    2012

    2012540

    Returns: 2010495

  6. 1

    25

    2

    25

    Returns: 19

  7. 362136128913

    9478364712

    44728

    7428164817412

    Returns: 7428164763281

  8. 99999999999

    99999999977

    2

    1000000000000000000

    Returns: 999999999989999999

  9. 99999999999

    99999999977

    123456789

    999999999769999999

    Returns: 999999999636543212

  10. 99999999999

    99999999977

    123456789

    999999999770000000

    Returns: 999999999636543212

  11. 99999999999

    99999999977

    123456789

    999999999770000001

    Returns: 999999999636543213

  12. 99999999977

    99999999977

    2

    1000000000000000000

    Returns: 0

  13. 11

    958961203200

    2

    10000

    Returns: 9999

  14. 11

    958961203200

    2

    999999999999999999

    Returns: 999966699966699965

  15. 3

    68719476736

    111111111111111111

    888888888888888888

    Returns: 388888888888888889

  16. 847288609443

    549755813888

    111111111111111111

    888888888888888888

    Returns: 388888888888888889

  17. 21

    2

    111111111111111111

    888888888888888888

    Returns: 388888888888888889

  18. 99

    4

    111111111111111111

    888888888888888887

    Returns: 388888888888888889

  19. 111

    256

    111111111111111111

    888888888888888889

    Returns: 388888888888888890

  20. 49

    14

    111111111111111110

    888888888888888888

    Returns: 388888888888888889

  21. 0

    1

    2

    1000000000000000000

    Returns: 0

  22. 0

    1

    2

    2

    Returns: 0

  23. 0

    1

    327164781268912469

    839217712678612863

    Returns: 0

  24. 0

    1000000000000

    3

    999999999999999997

    Returns: 0

  25. 0

    1000000000000

    540

    540

    Returns: 0

  26. 0

    999999999999

    129378689678269898

    919737816487154711

    Returns: 0

  27. 6

    7

    2

    4

    Returns: 3

  28. 45

    41

    28

    94

    Returns: 65

  29. 59

    519

    928

    963

    Returns: 36

  30. 5813

    2489

    1526

    6983

    Returns: 5456

  31. 39874

    83293

    56962

    86419

    Returns: 29457

  32. 261806

    53685

    315327

    624996

    Returns: 309653

  33. 1129440

    2544683

    8372502

    31083654

    Returns: 22711144

  34. 35695472

    21222021

    7618641798

    8774279486

    Returns: 1155637634

  35. 224373828

    776430048

    228350397336

    810524008713

    Returns: 582173575387

  36. 3625075800

    4082244305

    31025053940470

    72265575444757

    Returns: 41240521453775

  37. 5838070456

    7388262910

    63262651904782

    77924970676996

    Returns: 14662318768246

  38. 7308395075

    6181293934

    85013659966006

    90585807765077

    Returns: 5572147798171

  39. 97063184380

    85711963742

    533241116222959

    5831724689282439

    Returns: 5298483572935846

  40. 22226482333

    50837177762

    4238128539174614

    7324343505785954

    Returns: 3086214966550633

  41. 13676721976

    91863265235

    7278347179606431

    7838151833685873

    Returns: 559804654036786

  42. 616413512692

    344284905720

    315148875301650676

    332737260009667982

    Returns: 17588384707812960

  43. 229020880549

    719157259627

    231971125802989573

    250649081162131185

    Returns: 18677955359115641

  44. 62668576016

    841939978131

    713891923439452150

    943429244996903962

    Returns: 229537321486295623

  45. 717135519791

    8432101591

    700042863490303157

    873687154201095602

    Returns: 173644290690199206

  46. 999958000441

    999966000289

    100663296000000001

    908800000000000001

    Returns: 808135895849557444

  47. 999962000357

    999966000289

    209203200000000001

    826200000000000001

    Returns: 616996182992710877

  48. 999966000289

    999966000289

    180143985094819841

    809240558043136001

    Returns: 0

  49. 314159265358

    979323846264

    338327950288419716

    939937510582097494

    Returns: 601609560286306045

  50. 111111111111

    1000000000000

    99999999999999999

    899999999999999999

    Returns: 720000000000000001

  51. 333333333333

    1000000000000

    99999999999999999

    900000000000000000

    Returns: 720000000000000001

  52. 555555555555

    1000000000000

    99999999999999999

    900000000000000001

    Returns: 720000000000000002

  53. 777777777777

    1000000000000

    100000000000000000

    899999999999999999

    Returns: 720000000000000000

  54. 999999999999

    1000000000000

    100000000000000000

    900000000000000000

    Returns: 720000000000000000

  55. 777777777777

    1000000000000

    100000000000000000

    900000000000000001

    Returns: 720000000000000001

  56. 555555555555

    1000000000000

    100000000000000001

    899999999999999999

    Returns: 720000000000000000

  57. 333333333333

    1000000000000

    100000000000000001

    900000000000000000

    Returns: 720000000000000000

  58. 111111111111

    1000000000000

    100000000000000001

    900000000000000001

    Returns: 720000000000000001

  59. 973821738913

    100

    9

    999999999999999989

    Returns: 899999999999999983

  60. 912749124767

    1000

    9

    999999999999999990

    Returns: 899999999999999983

  61. 748129579201

    10000

    9

    999999999999999991

    Returns: 899999999999999984

  62. 789032859239

    100000

    10

    999999999999999989

    Returns: 899999999999999982

  63. 923805973283

    1000000

    10

    999999999999999990

    Returns: 899999999999999982

  64. 589329848177

    10000000

    10

    999999999999999991

    Returns: 899999999999999983

  65. 948489999389

    100000000

    11

    999999999999999989

    Returns: 899999999999999982

  66. 567237748239

    1000000000

    11

    999999999999999990

    Returns: 899999999999999982

  67. 772865832651

    10000000000

    11

    999999999999999991

    Returns: 899999999999999983

  68. 549755813888

    549755813888

    562949953421312

    576460752303423488

    Returns: 0

  69. 549755813888

    549755813888

    9007199254740992

    576460752303423488

    Returns: 0

  70. 835884417024

    626913312768

    839808

    701982420492091392

    Returns: 467988280327501056

  71. 940369969152

    660451885056

    705277476864

    592297667290202112

    Returns: 296148481006362624

  72. 708588000000

    933120000000

    6

    531441000000000000

    Returns: 478296899999999995

  73. 656100000000

    956593800000

    7290000000

    816293376000000000

    Returns: 544195579140000000

  74. 723350250000

    933897762000

    588000

    544876111954566000

    Returns: 467036667389124000

  75. 551353635000

    945177660000

    555660

    851014335622500000

    Returns: 709178613018286950

  76. 738213861000

    994328874000

    100

    649694486271600000

    Returns: 639850630418999902

  77. 724791790800

    781258401000

    76865250

    799164488433465000

    Returns: 784634224931934300

  78. 644787643500

    706611262500

    7362272736

    782562915027653760

    Returns: 777820102164378715

  79. 956553097500

    955338426900

    79204079955000

    622493227862906400

    Returns: 618061478162091600

  80. 861997739460

    631503422550

    501233692960

    557385854878125000

    Returns: 552076921704961259

  81. 888550637520

    558955940400

    944743800

    730260693522360000

    Returns: 730000350084718656

  82. 572363011220

    607585350372

    654182100

    799543631608984080

    Returns: 787956042100384560

  83. 946787353512

    935757172350

    6428773300950

    653359152745230750

    Returns: 651458947960416960

  84. 907210530576

    556933737360

    9604

    523096721843295600

    Returns: 522992207013746878

  85. 823861737006

    608941283874

    62790

    931057383468712500

    Returns: 876289302088140904

  86. 816054253560

    866469685000

    63881607625635800

    558089922311441520

    Returns: 494007824497292209

  87. 972497045520

    594710156040

    72072

    602950411333144875

    Returns: 582159017838828914

  88. 84179

    102101

    2

    1000000000000000000

    Returns: 999990205776632941

  89. 3

    12312367

    2

    1000000000000000000

    Returns: 999999918780848556

  90. 1

    3

    2

    1000000000000000000

    Returns: 666666666666666666

  91. 103006704005

    103046704706

    10000350600040006

    100020007000500401

    Returns: 90019656399586815

  92. 900700074773

    800700074773

    2

    999999999999

    Returns: 999999999997

  93. 1

    12

    99999999999999

    99999999999999999

    Returns: 83250000000000001

  94. 1234567890

    81480755400

    2

    100000000000000000

    Returns: 99999999926362980

  95. 1

    25

    5

    25

    Returns: 16

  96. 1000000000000

    99999999999

    2

    1000000000000000000

    Returns: 999999999969999999

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: