the number of integer point inside circle  is sigma(r*r/(4*i+1)-r*r/(4*i+3))
use stern borcot to cut hyperbola curve it can be done O(r^(2/3))

what do you mean by cut huperbola curve?

maybe we can directly use stern borcot tree to cut circle I think it is faster...

basic idea is use line segment (x1,y1) --->(x2,y2） with slope -a/b(a>0,b>0)  to cut quadric curve so that all of integer point strictly under this line segment is inside the quadric curve (x1,y1) and (x2,y2) is strictly outside the curve
if we know (x1,y1),(x2,y2) and -a/b  we can find next -(a1/b1) a/b and a1/b1 is neibour in stern borcot tree .it can be proved there are O(n^1/3) state  if the quadric curve is huperbola curve x*y==n

My solution convert this problem to compute simga(r*r/(4*i+1)-r*r/(4*i+3)) so it is huperbola curve (4*x+1)*y==r*r and (4*x+3)*y==r*r I have done twice ,so it is slow, dirctly cut circle only do once...

Edited by author 25.09.2018 21:34

Edited by author 25.09.2018 21:37

will try that for sure, I don't see any way I can speed up my current solutoin, I only need to calculate squares n-(n/sqrt(2)) times, and I do only +/- operations per iteration(no sqrt and multiplication/divisions). and for any n, it runs 0.75-0.8 sec on my pc, but I still get TLE18 here.

your computer is too strong,  ural oj O(1e9) can't fit into 2 sec

Edited by author 26.09.2018 20:03