LOVEA - EDITORIAL

PROBLEM LINKS:

Contest

Practice

DIFFICULTY:

Simple

EXPLAINATION

Problem [Toggle Candles] : After performing operation on 1 to 10^18 candles:

for i = 1 to 10^18 do :

Toggle the all candles which are multiple of i.

The answer is all candles no (i) which are perfect square will be turned on.

Mathematical reason is simple: only perfect square have odd number of divisors.

For eg . i = 16 : total 5 distinct divisors are

1 , 16

2 , 8

and 4

So initially candle is turned off and will be toggled odd no of times [ in this eg 5 times] , So it
will be turned on at the end.

So answer for each query is no of perfect squares in the range [L R].

ans = (int)sqrt(R)-(int)sqrt(L);

if(R is perfect square)ans = ans +1;

Key Point : c++ , java library SQRT function give wrong value at high range boundary case data. So
to get correct value of (int)sqrt(R) we can use binary search follows :

int tests = readINT();

for(int t=1;t<=tests;t++){

long L = readLong();

long R = readLong();

long left = sqrtLower(L);

long right = sqrtLower(R);

ans = right-left;

if(left*left==L) ans=ans + 1; //checking left perfect square.

out.write(“”+ans+“\n”);

}

public static long sqrtLower(long n)throws Exception{

long l = 1; long r = 2000000000L;

long mid=0;

while(l<=r){

mid = l + (r-l)/2;

if(mid*mid < n){

l = mid+1;

}else if(mid*mid==n){

return mid ;

}else{

r = mid-1;

}

}

return l-1;

}

Time Complexity : Big O(T*logN) where N = R-L = 10^18

Reference Solution

Setter Solution

Tester Solution

My solution: CodeRush 2015 – aleigorithms

Awesome problem and also editorial

Similar to this

I have question to this line: “if(R is perfect square)ans = ans +1;”.

Maybe you want to say:“if(L is perfect square)ans = ans +1;” ?