prob: https://atcoder.jp/contests/abc193/editorial/820
I’m able to understand the solution and the condition in for loop but I’m having difficulty in understanding the equation and how it is derived should I just ignore it
Help with understanding
the link I just sent it has the solution and the equation I asked about
Yes got it so what you are not able to understand the code?
not able to understand the equation
as we have to express the number in the form of a^b so for this we will checkk for only those number in which this expression evaluates should be less then N thats why we will check for the numbers in the range from 2 to the range such that the number’s square should be less than N only.
the equation says this only and in the code just according to the equation we are marking the powers of that number in the while loop as expressable.
how did we get the term logN as the upper limit of x in the summation
because for every number we are checking upto the range of the square root of that number.
Actually if we go deeper into this then the square root and log(n) are not the same but they are nearly equal.
check this image when we are taking the upper bound as log(N) because the range for the both is different but the we can find the correct answer for log(N) as well.