数论出题组比赛用题：圆点
T2:圆点
思考难度：提高?
代码难度：普及?
首先有结论：半径R\sqrt{R}R的圆经过的整点数是4∑d∣Rχ(d)4\sum_{d|R}\chi(d)4∑d∣Rχ(d)，其中χ(d)=1 (d​​mod  4=1), −1 (d​​mod  4=3), 0 (d​​mod  2=0).\chi(d)=1~(d\!\!\mod 4=1),~-1~(d \!\!\mod 4 =3),~0~(d \!\!\mod 2=0).χ(d)=1 (dmod4=1), −1 (dmod4=3), 0 (dmod2=0).
所以答案是
4∑i=1Ri∑d∣iχ(d)4\sum_{i=1}^{R}i\sum_{d|i}\chi(d)4i=1∑Rid∣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∑Rd×χ(d)i=1∑⌊dn⌋i
然后就可以O(R)O(\sqrt{R})O(R)计算了。
查看17道真题和解析
投递深圳虾皮信息科技有限公司等公司10个岗位
