Thanks a lot that helped me, I have struggled for this problem from last 2 days with so many WA
your EPS is probably too small. try increasing it, as you only need the integer part of the root.
i think your o[] vector is wrong. o[1] should be 10^18, o[2] =sqrt(10^18)=10^9 ⌠you missed the first root: no root at all => j = 1
@caioaao-thanks for answering, but in the code, o[j] contains the overflow value x such that x^(j+1) is just less than or equal to 10^18
(my code works for the test case given in the problem)
try this on your nth root implementation then, right after the while loop:
Yes it is possible.
To find the nth root of x, find y = pow(x, 1.0/n)
Because of precision errors, the answer could be either y rounded up or down. So lo = y and hi = (y+0.5)
Check if pow(hi, n) <= x, if yes, hi is the root else lo is the root.
2 pow calls to find one root.
I managed to get AC with that CodeChef: Practical coding for everyone
the only thing I can see thatâs different in your implementation is that youâre not testing if ans < 0 (see first two comments in CodeChef: Practical coding for everyone).
try printing (ans+MOD)%MOD to ensure itâll never be negative. other than that I canât see anything wrong in your implementation, and all Iâve tested using your code gives the same output as my AC implementation.
@sudip1401
i did something on the similar lines but am getting tleâŚ
why?
http://www.codechef.com/viewsolution/4108853
@tyler_durden Youâre calling pow(x,r) twice. Call it once and store it. And donât use the floor and ceil functions, theyâre an overhead, simply assign to the LL variable to get floor and +0.5 to get ceil. If it still gets TLE, use scanf printf instead of cin cout.
you are repeatedly computing for the sum of a[60] to a[n] each queryâŚ
you can precalculate the sum before entering the queryâŚ