How to check if a number n is of the form a^b.

problem link https://www.codechef.com/problems/APOWB

Simple idea is to precompute a set containing all powers >= 2nd power of all numbers from 2 to 1e5. This will solve problem for input values upto 1e10 because minimum value of b is 2.

Now, for values of a > 1e5, we realize that 4th power of a will always be > 1e16, but in input, all N <= 1e16.

So, we will alsot take square root and cube root, and check if sqrt*sqrt == N || cbrt*cbrt*cbrt == N || set.contains(N)…

If any of above is true, answer is true.

Hope u find this helpful…

1 Like