和亿维

Mobius127 · 2025-10-21 11:51:36 · 题解

神秘写法。

如无特殊说明，除在计算最终答案时，其他计算只涉及第一象限（不包括坐标轴）内的整点。

考虑模拟 DIVCNT1 的做法（建议先写这个）。

我们需要计算 \sum_{i=1}^{n} \lfloor\sqrt{n^2-i^2}\rfloor，即 f(x)=\sqrt{n^2-i^3} 图像以下的整点数量，按 x+g(x)=n 对称，得到 h(x)=n-\sqrt{2nx-x^2}。直接套 DIVCNT1 的做法就行了。我不会告诉你这样做是因为我正常写一直写假

为了 SBT 二分正常进行，我们仍从对称处计算（保证斜率绝对值递减且在 [0, 1] 范围内），设 B=\lfloor n(1-\frac{\sqrt{2}}{2}) \rfloor，取点 (B, B)，容易发现无非两种情况：

则取第一个不在图像内的点，从这个点开始向右下拟合曲线计算答案，方法与 DIVCNT1 没有任何区别，在 SBT 上二分下一步的向量，退出条件为 k\ge h'(x+mid)。

计算最终答案时，分上面取的起始点进行分讨，假设拟合过程得到的整点数量为 cnt，则答案

原理是先计算 h(x) 以内的整点数（即 2cnt-\Delta c ），\Delta c 由起始点决定，是对称时（ 2cnt ） 算重的那些点。i(n) 则是第一象限中到原点距离恰好为 n 的点的数量。

以 n=8, 9 为例，容易得到 B 均为 3，实际计算的 cnt 都是 y=3 及以下部分的整点个数。

根据上图容易模拟出 \Delta c=(B-1)^2 \operatorname{or} B^2-1

不知道复杂度怎么证，据说打表出来点数是 O(n^{\frac{2}{3}}) 的。