统计半径为$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})$。