类欧几里得算法真是厉害
计算奇数的个数即可
$$ cnt = sum_{d = 1}^{n}{ lfloor {d sqrt{r}} floor - 2 lfloor frac{lfloor {d sqrt{r}} floor}{2} floor}$$
我们实际上要计算的是
$$sum_{d = 1}^{n}{lfloor frac{d(a sqrt{r} + b)}{c} floor}$$
令
$$x = lfloor frac{(a sqrt{r} + b)}{c} floor $$
$$b_1 = b - x imes c$$
$$Lim = lfloor frac{n(a sqrt{r} + b_1)}{c} floor$$
则
egin{eqnarray} sum_{d = 1}^{n}{lfloor frac{d(a sqrt{r} + b)}{c} floor}&=& xfrac{n(n + 1)}{2} + sum_{d = 1}^{n}{lfloor frac{d(a sqrt{r} + b_1)}{c} floor} onumber\ &=&xfrac{n(n + 1)}{2} + sum_{d = 1}^{n} {sum_{k = 1}^{infty}{k <= frac{d(a sqrt{r} + b_1)}{c}}} onumber\ &=&xfrac{n(n + 1)}{2} + sum_{k = 1}^{Lim} {sum_{d = 1}^{n}{d >= frac{ck}{a sqrt{r} + b_1}}} onumber\ &=&xfrac{n(n + 1)}{2} + Lim imes n - sum_{k = 1}^{Lim}{lfloor frac{k(casqrt{r} - cb_1)}{a^2r - b_1^2} floor} onumber end{eqnarray}
转化成子问题，递归解决
复杂度的话，每次减去整数部分，相当于分子对分母做类似取摸的操作（实数貌似没有定义取摸），每次分子至少减少一半，所以时间复杂度为$O(logn)$