每月一题2019.8

统计半径为$n$的圆内整点个数,$n\leq 10^{18}$。

题面

用$Stern-Brocot-Tree$可以很方便地处理这一类问题。

用折线拟合函数有两个要求:

$1$、函数是个凹函数。

$2$、函数可以快速求导。

对于圆而言,只需要统计第一象限内的整点个数。

为了使函数转化成凹函数,就将其旋转$180$度,就变成了凹函数,然后容斥计算即可。

这时圆的解析式就变成了$(x-n)^2+(y-n)^2=n^2$。

随手写成:$y=n+\sqrt{2nx-x^2}$。

求个导:$\frac{n-x}{\sqrt{2nx-x^2}}$。

那么就可以愉快地计算了,复杂度$O(n^{1/3})$。