DivisorsPower
SRM 628 · 2014-06-16 · by w10d
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
Constraints
- n will be between 2 and 10^18, inclusive.
4 Returns: 2
d(2) = 2, h(2) = 4
10 Returns: -1
There is no x satisfying h(x) = 10.
64 Returns: 4
d(4) = 3, h(4) = 64
10000 Returns: 10
d(10) = 4, h(10) = 10000
2498388559757689 Returns: 49983883
66535302272909312 Returns: -1
Program with overflow would return 60.
8279638877935441 Returns: -1
This test fails if program treats 9539*9539 as a prime.
118721967032369152 Returns: -1
Program with overflow would return 210.
759807991618519296 Returns: -1
Program with overflow would return 370.
Submissions are judged against all 98 archived test cases, of which 9 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DivisorsPower with a public method long long findArgument(long long n) · 98 test cases · 2 s / 256 MB per case