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

T2:圆点

思考难度：提高?

代码难度：普及?

首先有结论：半径R\sqrt{R}R​的圆经过的整点数是4∑d∣Rχ(d)4\sum_{d|R}\chi(d)4∑d∣R​χ(d)，其中$$\chi (d)=1(d\mathrm{m}\mathrm{o}\mathrm{d}4=1),-1(d\mathrm{m}\mathrm{o}\mathrm{d}4=3),0(d\mathrm{m}\mathrm{o}\mathrm{d}2=0).$$

所以答案是

4∑i=1Ri∑d∣iχ(d)4\sum_{i=1}^{R}i\sum_{d|i}\chi(d)4i=1∑R​id∣i∑​χ(d)

=4∑d=1Rd×χ(d)∑i=1⌊nd⌋i=4\sum_{d=1}^{R}d\times \chi(d)\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor}i=4d=1∑R​d×χ(d)i=1∑⌊dn​⌋​i

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