# Doubts with this approach for TWOVRIBL

How come this approach works even though it performs more than 10^9 operations?
https://www.codechef.com/viewsolution/25391464
P is incremented by 1 each time.
So for a input :
1
1000000000

It performs more than 10^9 operations.
For time limit 1sec we are supposed to keep a upper bound of 10^8 operations, or not?

No it doesn’t really perform 10^9 operations, since you are squaring it will actually take less iterations to reach Xf

Look at the lines 27 to 32
while(p<=cur)
{
ans++;
y+=`p*p`;
while(`p*p`<=y) {p++;}
}
at line 31, we are incrementing the value P by 1 each time in the while loop,
not squaring it

Since outer loop will run till p<=Xf, so this program performs atleast Xf number of operations,

yes, so imagine how would the condition look like. I’ll explain with an example.
let xf=100
at p=1 (11<100)
at p=2 (2
2<100)
.
.
.
at p=6 (66<100)
at p=7 (7
7<100)
at p=10 (10*10<100)

at this increases fast so for xf=100 it took just 10 i.e √n iteration

I hope you are getting what i’m trying to say ?

Bro, the condition compares with ‘Y’ not with ‘Xf’
P is being compared with Xf…not `P*P`