好简洁的题面。

$$\begin{aligned} &\sum_{d=1}^n(-1)^{\lfloor\sqrt{d\times r\times d}\rfloor} \\=&\sum_{d=1}^n(-1)^{\lfloor d\sqrt r\rfloor} \\=&-n+2\sum_{d=1}^n[2|\lfloor d\sqrt r\rfloor] \end{aligned} $$$$\begin{aligned} &\sum_{d=1}^n[2|\lfloor d\sqrt r\rfloor] \\=&\sum_{j=0}^{\lfloor n\sqrt r\rfloor}(-1)^j\sum_{d=1}^n[rd^2\ge j^2]&([2|\lfloor\sqrt m\rfloor]=\sum_j(-1)^j[m\ge j^2] ) \\=&\sum_{j=0}^{\lfloor n\sqrt r\rfloor}(-1)^j(n-\sum_{d=1}^n[rd^2<j^2]) \\=&n[2|\lfloor n\sqrt r\rfloor]-\sum_{j=1}^{\lfloor n\sqrt r\rfloor}(-1)^j\sum_{d=1}^n[rd^2<j^2] \end{aligned} $$$$\begin{aligned} &\sum_{j=1}^{\lfloor n\sqrt r\rfloor}(-1)^j\sum_{d=1}^n[rd^2<j^2] \\=&\sum_{j=1}^{\lfloor n\sqrt r\rfloor}(-1)^j\lfloor\sqrt{(j^2-1)/r}\rfloor \\=&[2\nmid[\lfloor n\sqrt r\rfloor]]+\sum_{j=1}^{\lfloor n\sqrt r\rfloor}(-1)^j\lceil\sqrt{j^2/r}\rceil \end{aligned} $$

设 $\sqrt r\sim p/q$，使得把 $p/q$ 代入后答案相同或相近。显然当误差达到 $O(n^{-1})$ 级别时就比较稳了。这个可以用 SBT 二分暴力找。

$$\sum_{j=1}^{\lfloor n\sqrt r\rfloor}(-1)^j\lceil jq/p\rceil $$

奇偶分开处理就是类欧板子了。