1. 题意翻译

给定三个非负整数 a,b,k，集合

$$S = {a, a+1, \ldots, b}$$

定义

$$T = {(x, y) \mid x \in \mathbb{N},\ y \in \mathbb{N},\ x^2 \in S,\ y^3 \in S,\ |x^2 - y^3| \le k} $$

其中 N 表示非负整数（通常包括 0，但这里 a≥1，所以 x,y 至少是 1 的情况）。

要求计算 $\lvert T \rvert$，即满足条件的 (x,y) 对的数量。

---

2. 条件分析

条件为： 1.$x^2 \in S$，即 $a \le x^2 \le b$。 2.$y^3 \in S$，即 $a \le y^3 \le b$。 3.$|x^2 - y^3| \le k$。

---

3. 直接枚举的不可行性

数据范围 a,b≤$10^{18}$ ，意味着 x 最大可能到 $10^9$ 左右，y 最大可能到 $10^6$左右，因为： $x_{\max} \approx \sqrt{b} \approx 10^9$，$y_{\max} \approx \sqrt[3]{b} \approx 10^6$。 如果直接枚举 x 和 y，复杂度为 O($\sqrt{b}$⋅$\sqrt[3]{b}$)，最坏情况 $10^9×10^6=10^{15}$不可接受。

---

4. 优化思路

注意到 $|x^2 - y^3| \leq k$意味着：

$$y^3 - k \leq x^2 \leq y^3 + k$$

我们可以枚举 y，因为 y 的范围较小（最多 $10^6$级别）。

对于每个 y，计算 $y^3$ ，然后找满足 $a \leq x^2 \leq b$且$x^2$在区间 $[y^3 - k, y^3 + k]$ 内的整数 x。

4.1 枚举

y 的范围 y 需满足 $a \leq y^3 \leq b$ ，所以：

$$y_{\min} = \lceil a^{1/3} \rceil，y_{\max} = \lceil b^{1/3} \rceil $$

这里注意 y 是自然数（从 0 还是 1 开始？题中 a≥1，所以 y=0 时 $y^3=0$不在 S 中，除非 a=0 但 a≥1，所以 y≥1）。

4.2 对于固定的 y，求 x 的范围

条件：

$$\max(a, y^3 - k) \le x^2 \le \min(b, y^3 + k)$$

并且 x 是自然数。

设：

$$L = \max(a, y^3 - k)，R = \min(b, y^3 + k)$$

如果 L>R，则没有 x 满足条件。

否则，x 的范围是：

$$x_{\min} = \lceil \sqrt{L} \rceil，x_{\max} = \lceil \sqrt{R} \rceil $$

然后这个 y 贡献的数目是 $\max(0, x_{\max} - x_{\min} + 1)$。

4.3 特殊情况 k=0

当 k=0 时，条件变成 $x^2=y^3$ ，即求 $x^2=y^3$ 的自然数解。 设 $x=t^3，y=t^2$，只需枚举 t 使得 $a \leq t^6 \leq b$ ，然后数 t 的个数即可。

---

5. 算法步骤

1.若 k=0： 计算 $ t_{\min} = \lceil a^{1/6} \rceil， t_{\max} = \lceil b^{1/6} \rceil $。

答案 =$\max(0, t_{\max} - t_{\min} + 1)$

2.若 k>0：

初始化 ans=0。

计算 $y_{\min} = \lceil a^{1/3} \rceil，y_{\max} = \lceil b^{1/3} \rceil$

对每个 $y \in [y_{\min}, y_{\max}]$: 计算 ycube=$y^3$ 。

L=max(a,ycube−k)，R=min(b,ycube+k)。

如果 L>R，跳过。 $x_l = \lceil \sqrt{L} \rceil，x_r = \lceil \sqrt{R} \rceil$

如果 xl≤xr，则 ans+=(xr−xl+1)。

输出 ans。

---

6. 复杂度分析

k=0 时：直接计算 O(1)。

k>0 时：枚举 y 的个数最多 O(($b^{1/3}$-$a^{1/3}$)+1)，当 b=$10^{18}$ 时，$y_{\max}$=$10^{16}$，可接受。

---

7. 最终公式

$$\text{Answer} = \begin{cases} \max\left(0, [ \sqrt[6]{b} ] - [ \sqrt[6]{a} ] + 1 \right), & k = 0 \\ \sum_{y = \lceil a^{1/3} \rceil}^{\lfloor b^{1/3} \rfloor} \max\left(0, \left\lfloor \sqrt{\min(b, y^3 + k)} \right\rfloor - \left\lceil \sqrt{\max(a, y^3 - k)} \right\rceil + 1 \right), & k > 0 \end{cases} $$