Statistics

Problem Statement for "DivisorsPower"

Problem Statement

Halina is a young mathematician. Recently she has been studying an interesting function h that operates on positive integers.

Let d(n) be the number of distinct positive divisors of n. The function h is then defined as follows: for each n we have h(n) = n^d(n). In words, h(n) is defined as n to the power of d(n).

For example, d(6)=4 because 6 is divisible by 1, 2, 3, and 6. Then, h(6) = 6^4 = 1296.

Halina already knows how to compute her function h. Now she would like to compute the inverse function. Help her!

You are given a long n. Return the smallest x such that h(x) = n. If there is no such x, return -1 instead.

Definition

Class:
DivisorsPower
Method:
findArgument
Parameters:
long
Returns:
long
Method signature:
long findArgument(long n)
(be sure your method is public)

Constraints

  • n will be between 2 and 10^18, inclusive.

Examples

  1. 4

    Returns: 2

    d(2) = 2, h(2) = 4

  2. 10

    Returns: -1

    There is no x satisfying h(x) = 10.

  3. 64

    Returns: 4

    d(4) = 3, h(4) = 64

  4. 10000

    Returns: 10

    d(10) = 4, h(10) = 10000

  5. 2498388559757689

    Returns: 49983883

  6. 25

    Returns: 5

  7. 729

    Returns: 9

  8. 27

    Returns: -1

  9. 81

    Returns: -1

  10. 50

    Returns: -1

  11. 7921

    Returns: 89

  12. 1048576

    Returns: 16

  13. 110075314176

    Returns: 24

  14. 456976

    Returns: 26

  15. 456977

    Returns: -1

  16. 656100000000

    Returns: 30

  17. 531441

    Returns: 27

  18. 101559956668416

    Returns: 36

  19. 1062882

    Returns: -1

  20. 9682651996416

    Returns: 42

  21. 64925062108545024

    Returns: 48

  22. 96717311574016

    Returns: 56

  23. 66535302272909312

    Returns: -1

    Program with overflow would return 60.

  24. 8279638877935441

    Returns: -1

    This test fails if program treats 9539*9539 as a prime.

  25. 360040606269696

    Returns: 66

  26. 3486784401

    Returns: 81

  27. 10460353203

    Returns: -1

  28. 1000000000000000000

    Returns: 100

  29. 28525864220672256

    Returns: 114

  30. 1771561

    Returns: 121

  31. 118721967032369152

    Returns: -1

    Program with overflow would return 210.

  32. 759807991618519296

    Returns: -1

    Program with overflow would return 370.

  33. 4890838206582784

    Returns: 412

  34. 53974440976

    Returns: 482

  35. 292681

    Returns: 541

  36. 541

    Returns: -1

  37. 29542602396307456

    Returns: 556

  38. 347709076131545088

    Returns: -1

  39. 594823321

    Returns: 841

  40. 3533050288881

    Returns: 1371

  41. 9109555799784049

    Returns: 208849

  42. 9598548249896761

    Returns: 212521

  43. 9598548249896762

    Returns: -1

  44. 999922001521

    Returns: 999961

  45. 35044572243972880

    Returns: -1

  46. 982134461213542729

    Returns: 994009

  47. 838137706742929321

    Returns: 942841

  48. 889092468889

    Returns: 942917

  49. 324584056305938521

    Returns: 687241

  50. 6756327210616080

    Returns: -1

  51. 329734774403186161

    Returns: 23963

  52. 893623315422378256

    Returns: 30746

  53. 95367431640625

    Returns: 625

  54. 79792266297612001

    Returns: 2401

  55. 61341990221615104

    Returns: 628

  56. 965206487562694441

    Returns: 982449229

  57. 926680334444501641

    Returns: 962642371

  58. 926680334444501643

    Returns: -1

  59. 926680338295071129

    Returns: -1

  60. 98978104944563881

    Returns: 314607859

  61. 999999874000003969

    Returns: 999999937

  62. 999999999999999989

    Returns: -1

  63. 2

    Returns: -1

  64. 999999999999

    Returns: -1

  65. 12345679432098769

    Returns: 111111113

  66. 16

    Returns: -1

  67. 999999999999999996

    Returns: -1

  68. 68

    Returns: -1

  69. 999999858000005041

    Returns: 999999929

  70. 100000000000000003

    Returns: -1

  71. 965211250482432409

    Returns: 982451653

  72. 999998002000998001

    Returns: 999999001

  73. 1014741853230169

    Returns: 100489

  74. 999999992000000016

    Returns: -1

  75. 8

    Returns: -1

  76. 36902422678601089

    Returns: 332929

  77. 1125899839733759

    Returns: -1

  78. 36

    Returns: -1

  79. 10000000002065383

    Returns: -1

  80. 127021550911887241

    Returns: 502681

  81. 999999999999999877

    Returns: -1

  82. 485829216265306112

    Returns: -1

  83. 1073741824

    Returns: 32

  84. 1000000

    Returns: -1

  85. 4294967297

    Returns: -1

  86. 14774554437890625

    Returns: 105

  87. 789730223053602816

    Returns: -1

  88. 32894113444921

    Returns: 32041

  89. 10028029413722401

    Returns: -1

  90. 999999594000041209

    Returns: 999999797

  91. 486820867825729536

    Returns: -1

  92. 999999999999998989

    Returns: -1

  93. 2498388559757699

    Returns: -1

  94. 632070858021803281

    Returns: 795028841

  95. 11

    Returns: -1

  96. 999999866000004473

    Returns: -1

  97. 999999999999999999

    Returns: -1

  98. 2985984

    Returns: 12

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: