I am practicing problems from past contests. I opened the first contest of 2014 which was conducted by IIT Madras. I opened the question which had most number of submissions assuming it to be easy as compared to others but in this question they are asking to check whether a no. lets say N is of the form a^b or not where a,b>=2 and N<=10^16 within 1 sec time limit .
First I thought I will pre compute all the no. of the form a^b and save them in array as 1 and just look for A[N] in the array if it is 1 then YES otherwise NO but computing no. upto 10^16 will take a lot of time it will get TLE .
I searched for editorial of this problem but now its not there ,then I opened the submissions of other people but still I am not getting their approach ,can someone please help me how to do this one or do this require some new logic which I don’t know .
Link to the problem -
This should be done using precomputation of powers only but some optimization.
For n upto 10^16, there will be atmost 10^8 "a"s will be there in worst case.
This is when b = 2, so storing all of them and processing, which will not pass the TL. So we divide this problem into 2 cases
- Whether n is a^2 for some “a>=2” or
- n is a^b for a>=2, b > 2
Case1: you use sqrt(n) function to find “a”. that is a = (int)sqrt(n).
Then u check whether a*a is n or not (Here Do carefully because precision matters)
Case2: Here we do this by precomputation of powers of all "a = {2, 3, 4, … cuberoot(10^16)}"s starting with b = 3 until a^b < 10^16.
you store all the precomputed powers in a set or vector. If you use a set then they will be sorted already,
if you use a vector then sort() the entire vector.
Once precomputation is done. Then use binary_search() for “n”. so takes logarithmic time.
That’s easy, prime factorize N and see that if each prime factor appears the same number of times or not.