Problem Link: CodeChef: Practical coding for everyone
Let’s fix some power p. It’s obvious that there are no more than 
numbers x such that x p does not exceed 1018. At the same time, only for p = 2 this amoung is relatively huge; for all other p ≥ 3 the total amount of such numbers will be of the order of 106.
Let’s then generate all of them and dispose of all perfect squares among them. Then answer to query (L, R) is equal to the amount of generated numbers between L and R plus some perfect squared in range. The first value can be calculated via two binary searches. The second one is 
. Note that due to precision issues the standard sqrt might produce incorrect values, so you can use additional binary searches instead.
Complexity: 
.