数论出题组比赛用题：圆点

T2:圆点

思考难度：提高?

代码难度：普及?

首先有结论：半径 $\sqrt{R}$R ​的圆经过的整点数是 $4{\sum }_{d\mid R}\chi \left(d\right)$4∑d∣R​χ(d)，其中 χ(d)=1 (dmod4=1), −1 (dmod4=3), 0 (dmod2=0).

所以答案是

$4\sum _{i=1}^{R}i\sum _{d\mid i}\chi \left(d\right)$4i=1∑R​id∣i∑​χ(d)

$=4\sum _{d=1}^{R}d\times \chi \left(d\right)\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }i$=4d=1∑R​d×χ(d)i=1∑⌊dn​⌋​i

然后就可以 $O\left(\sqrt{R}\right)$O(R ​)计算了。