I am trying to solve a problem on codeforces, to be precised, this problem. I was able to figure out that the solution is $N(n) - N(n-1)$ where $N(n)$ is the number of lattice points withing a circle centered at the origin. I wrote a solution using the formula from MathWorld.WolframAlpha
$$N(r) = 1 + 4\lfloor r\rfloor + \sum^{\lfloor r\rfloor}_{i = 1} \lfloor \sqrt{r^2 - i^2}\rfloor$$
Since $r$ is an integer in this case, I didn't bother much about the precision.
Here is the code I wrote.
long long N(int r){
long long s = 0;
for(int i = 1; i<=r; i++) s+=(int)sqrt(r*r-i*i);
s*=4;
s+=1+4*r;
return s;
}
This function worked well for small integers but failed for larger ones. I can't figure out why.
I inspected accepted submissions from other coders and I found out some of them used a simplified version of $N(n) - N(n-1)$, more precisely
$$N(n) - N(n-1) = 4\lfloor n\sqrt 2\rfloor$$
which I tried to derive and couldn't.
I am more interested in knowing how to simplify to get the expression but if anyone understands why the code fails, I'd really appreciate that as well. Thanks.