逛B站看到的
隐藏在素数规律中的π
从结论来讲，半径为$\sqrt n$的圆周上的整点个数是
$$ 4\sum_{d|n}\chi(d)$$
其中
$$ \chi(n)=\left\{
\begin{array}{rcl}
1 & & {n~mod~4~=~1}\\
-1 & & {n~mod~4~=~3}\\
0 & & {n~mod~2~=~0}
\end{array} \right. $$
因而半径为$\sqrt n$的圆内整点个数是
$$4\sum_{i=1}^n\sum_{d|i}\chi(d)=\\
4\sum_{d=1}^n\chi(d)\lfloor \frac{n}{d}\rfloor
$$
可以$O(\sqrt n)$算
UPD:
woc
我突然发现for一边算算上下界就是$O(\sqrt n)$了，因而上面那个做法完全没有卵用…