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) = 4n\sqrt 2$$

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.

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.