Statistics

Problem Statement for "SemiPerfectPower"

Problem Statement

Magical Girl Iris loves perfect powers. A positive integer n is a perfect power if and only if there are positive integers b > 1 and c > 1 such that b^c = n (where ^ denotes exponentiation). For example, 8 (=2^3) and 243 (=3^5) are perfect powers, while 1 and 54 are not.
One day, Iris discovered that there are very few perfect powers. To avoid being disappointed, she quickly invented the semi-perfect powers: A positive integer n is a semi-perfect power if and only if there are positive integers a >= 1, b > 1, and c > 1 such that a < b and a*(b^c) = n. For example, 243 (=1*3^5) and 54 (=2*3^3) are semi-perfect powers, while 1 and 24 are not.
Note that for some semi-perfect numbers there may be more than one corresponding triple (a,b,c). For example, 432 can be expressed as 2*6^3, but also as 3*12^2.
You are given longs L and R. Calculate and return the number of semi-perfect powers that lie between L and R, inclusive.

Definition

Class:
SemiPerfectPower
Method:
count
Parameters:
long, long
Returns:
long
Method signature:
long count(long L, long R)
(be sure your method is public)

Constraints

  • L will be between 1 and 8*10^16, inclusive.
  • R will be between L and 8*10^16, inclusive.

Examples

  1. 18

    58

    Returns: 9

    There are 9 semi-perfect powers between 18 and 58, inclusive: 18, 25, 27, 32, 36, 48, 49, 50, and 54.

  2. 1

    10

    Returns: 3

    Note that 1 is not considered to be a semi-perfect power.

  3. 80000000000000000

    80000000000000000

    Returns: 1

  4. 60

    70

    Returns: 1

    The number 64 is the only semi-perfect power in the given range. Note that there are multiple ways to choose a, b, and c when showing that 64 is a semi-perfect power. Still, each semi-perfect power should only be counted once.

  5. 319268319114310

    35860463407469139

    Returns: 95023825161

  6. 1

    80000000000000000

    Returns: 169502909978

  7. 1

    69

    Returns: 14

  8. 34

    68

    Returns: 6

  9. 5

    63

    Returns: 12

  10. 84

    98

    Returns: 1

  11. 9

    21

    Returns: 3

  12. 31849607

    57407119

    Returns: 44873

  13. 14017744

    23918885

    Returns: 23217

  14. 44063817

    76360651

    Returns: 51162

  15. 78329202

    99967971

    Returns: 30020

  16. 54100547

    73407666

    Returns: 29894

  17. 55311242

    92415045

    Returns: 54908

  18. 72874298

    94715914

    Returns: 30916

  19. 72778929

    98073924

    Returns: 35589

  20. 46437950

    73269079

    Returns: 42507

  21. 2833965

    85252057

    Returns: 161562

  22. 46190741699052806

    67733036572199814

    Returns: 34160524941

  23. 12112855692187609

    29181223013456925

    Returns: 38379773430

  24. 33939445586068479

    71305451785567572

    Returns: 61273662700

  25. 46871810212754106

    74399807860236297

    Returns: 42803279740

  26. 62420974775383685

    67509135665283420

    Returns: 7702458586

  27. 5824733599103901

    39604704739445767

    Returns: 76517415269

  28. 743532385627680

    32226984083142172

    Returns: 84969168043

  29. 5443566669391714

    20375808408964867

    Returns: 39857359439

  30. 40493616388582335

    52841161617685295

    Returns: 20897490053

  31. 33198479020484984

    65240317998868052

    Returns: 53640621452

  32. 37325743723718344

    60145622370456472

    Returns: 38174723791

  33. 38686218556549995

    53252237911488722

    Returns: 24790544079

  34. 45662840068636335

    78984324561761105

    Returns: 51418686450

  35. 28067644372112079

    48506091582055639

    Returns: 37103589348

  36. 78878342151559849

    79690035745831229

    Returns: 1149633528

  37. 8434629979432919

    79999999999939925

    Returns: 131655410918

  38. 24740012557260502

    79999999999976979

    Returns: 91970567444

  39. 11490939116480213

    79999999999996264

    Returns: 122994692514

  40. 41787776013501378

    79999999999978479

    Returns: 59550563217

  41. 34564735192345886

    79999999999967552

    Returns: 72613551683

  42. 67156370923643774

    77035406598618552

    Returns: 14447805752

  43. 67156370923643774

    77035406598618551

    Returns: 14447805751

  44. 26415459570585660

    41603293758250728

    Returns: 28635275938

  45. 26415459570585660

    41603293758250727

    Returns: 28635275937

  46. 11183036362767449

    22858043515038816

    Returns: 27876024189

  47. 11183036362767449

    22858043515038815

    Returns: 27876024188

  48. 50957548729141882

    63091978580011250

    Returns: 19199592726

  49. 50957548729141882

    63091978580011249

    Returns: 19199592725

  50. 57420090818586

    87622207806106

    Returns: 442856938

  51. 57420090818586

    87622207806105

    Returns: 442856937

  52. 28488411398213057

    49265843072654208

    Returns: 37527496226

  53. 28488411398213057

    49265843072654207

    Returns: 37527496225

  54. 2812016688577424

    46396182126919680

    Returns: 99689369913

  55. 2812016688577424

    46396182126919679

    Returns: 99689369912

  56. 5764502197702350

    12459004168420800

    Returns: 19715695921

  57. 5764502197702350

    12459004168420799

    Returns: 19715695920

  58. 13962602974240976

    58559371926951168

    Returns: 84725115278

  59. 13962602974240976

    58559371926951167

    Returns: 84725115277

  60. 12637349280232745

    29301438582197275

    Returns: 37237055770

  61. 12637349280232745

    29301438582197274

    Returns: 37237055769

  62. 61015905215027288

    63936280601226990

    Returns: 4478536503

  63. 61015905215027288

    63936280601226989

    Returns: 4478536502

  64. 2191332894443650

    4899697676475300

    Returns: 10937683310

  65. 2191332894443650

    4899697676475299

    Returns: 10937683309

  66. 12238779075337331

    16976765917299168

    Returns: 11819779719

  67. 12238779075337331

    16976765917299167

    Returns: 11819779718

  68. 102340687504686

    1434895578707070

    Returns: 9624460366

  69. 102340687504686

    1434895578707069

    Returns: 9624460365

  70. 7309150784006160

    21549697604276589

    Returns: 36314494497

  71. 7309150784006160

    21549697604276588

    Returns: 36314494496

  72. 6541395226588711

    30645268843465458

    Returns: 57471102243

  73. 6541395226588711

    30645268843465457

    Returns: 57471102242

  74. 18444337907547612

    18884282077899884

    Returns: 1009407167

  75. 18444337907547612

    18884282077899883

    Returns: 1009407166

  76. 9127952455383563

    12253421560354021

    Returns: 8649436903

  77. 9127952455383563

    12253421560354020

    Returns: 8649436902

  78. 5075701321471403

    9095062320360225

    Returns: 12816932613

  79. 5075701321471403

    9095062320360224

    Returns: 12816932612

  80. 44213934421566124

    63412335618014771

    Returns: 31017483826

  81. 44213934421566124

    63412335618014770

    Returns: 31017483825

  82. 27904541531726883

    77209355251245568

    Returns: 81530694018

  83. 27904541531726883

    77209355251245567

    Returns: 81530694017

  84. 3694887509961997

    12447245524130465

    Returns: 27217737980

  85. 3694887509961997

    12447245524130464

    Returns: 27217737979

  86. 38772629731820060

    53045484806688256

    Returns: 24300498821

  87. 38772629731820060

    53045484806688255

    Returns: 24300498820

  88. 28532810300017

    35127443797056

    Returns: 126978317

  89. 28532810300017

    35127443797055

    Returns: 126978316

  90. 35572926566420181

    39885268107418188

    Returns: 7826306973

  91. 35572926566420181

    39885268107418187

    Returns: 7826306972

  92. 2380011854108224

    34018837916661261

    Returns: 79578824718

  93. 2380011854108224

    34018837916661260

    Returns: 79578824717

  94. 47597558975003663

    72929590642682568

    Returns: 39447489319

  95. 47597558975003663

    72929590642682567

    Returns: 39447489318

  96. 3098117884989213

    27912981496131584

    Returns: 64608301825

  97. 3098117884989213

    27912981496131583

    Returns: 64608301824

  98. 37676138715431278

    47144080958896251

    Returns: 16537220754

  99. 37676138715431278

    47144080958896250

    Returns: 16537220753

  100. 13154282814725555

    37930424081572032

    Returns: 52186391619

  101. 13154282814725555

    37930424081572031

    Returns: 52186391618

  102. 7445822431144814

    17002745423307288

    Returns: 25555656678

  103. 7445822431144814

    17002745423307287

    Returns: 25555656677

  104. 3012605304450906

    3130068891268125

    Returns: 492017718

  105. 3012605304450906

    3130068891268124

    Returns: 492017717

  106. 6901680655528255

    8565191888160015

    Returns: 5124826288

  107. 6901680655528255

    8565191888160014

    Returns: 5124826287

  108. 8407637695404721

    12129901968827096

    Returns: 10449338410

  109. 8407637695404721

    12129901968827095

    Returns: 10449338409

  110. 11425959667121997

    18223302381986250

    Returns: 16907922308

  111. 11425959667121997

    18223302381986249

    Returns: 16907922307

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: