1398. Is It a Perfect Power, and How High

For each query decide whether n can be written as a^b with integers a >= 2 and b >= 2. If it can, print the pair with the largest b. Otherwise print -1.

n = 64 -> 2 6 since 64 = 2^6, and 4^3 and 8^2 also work n = 81 -> 3 4 n = 2 -> -1 n = 1000000000000000000 -> 10 18

The largest b pins the answer uniquely. 64 is 2^6, 4^3 and 8^2, and only the first has b = 6, so there is nothing left to choose.

## What most people try first

Take pow(n, 1.0 / b), round it, and compare. That is wrong, and it is wrong in a way that looks fine on small inputs. A double carries 53 bits of mantissa, so a value near 10^18 is already beyond the point where consecutive integers are representable. pow can land one below or one above the true root, so a genuine perfect power is reported as -1, or a value one away from a perfect power is reported as one. Rounding does not repair it, because the error can exceed half a unit.

## An exact integer root

For a fixed b, the map a -> a^b is strictly increasing on the positive integers, so the largest a with a^b <= n can be found by search. The search needs a power routine that cannot overflow, and this one stops the instant the running product would pass the cap:

pw(a, b, cap): r = 1 repeat b times: if r > cap / a: return -1 # the next multiply would pass cap r = r * a return r

The guard is a division, not a multiplication, so no value above cap is ever formed. Bracket the root by doubling while pw(2 * hi, b, n) still succeeds, which leaves the root in [hi, 2 * hi - 1], then binary search inside the bracket. Finally accept a only when pw(a, b, n) is exactly n.

## Why it is correct

a^b <= n with a >= 2 forces 2^b <= n, so b is at most 59 for n <= 10^18, and trying b from 60 downward and stopping at the first hit returns the largest valid exponent by construction. The bracket is sound because the doubling loop only ever grows hi while hi^b <= n, so the root is at least hi, and it stops when (2 * hi)^b > n, so the root is below 2 * hi.

## Overflow

n reaches 10^18, which needs 64 bits: a signed 32-bit integer stops at 2147483647. Any attempt to compute a^b and then compare is also a trap even in 64 bits, since a can be 10^9 and b can be 2 while a careless loop keeps multiplying past that. The division guard is what removes both problems. In JavaScript 10^18 is past 2^53, so the values are BigInt throughout.

## Cost

O(log^2 n) per query: at most 59 exponents, each a search of O(log n) steps whose test is O(b) multiplications with an early exit.

Constraints - `1 ≤ q ≤ 100` - `2 ≤ n ≤ 1000000000000000000`