自动搬运

查看原文

来自洛谷，原作者为

	Little_x_starTYJ 愿时光能缓，愿故人不散！ || 众所周知，如果把灯泡放在嘴里，即使你自己一个人也取得出来灯泡。

搬运于2025-08-24 23:04:57，当前版本为作者最后更新于2024-10-11 15:15:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

通俗题意

给你三个整数 $a, b, k$，需要你求出满足下列条件的不同的 $x, y$ 有多少对。

• $a\leq x^2, y^3 \leq b$。
• $|x^2 - y^3| \leq k$。
• $x, y$ 均为非负整数。

解题思路

注意到题目中一直在算平方和立方，所以可以猜测正确的时间复杂度应该是带有根号的。又观察到 $1\leq a \leq b \leq 10^{18}$，所以排除 $\mathcal{O}(\sqrt{n})$ 的算法，那么还有一种可能的时间复杂度就是 $\mathcal{O}(\sqrt[3]{n})$。

首先 $x, y$ 一定是在区间 $[\lceil\sqrt[3]{a}\rceil, \lfloor\sqrt[3]{b}\rfloor]$ 之间的。为什么要加上向上取整与向下取整呢？因为 $x, y$ 为整数，那么当 $y = \lfloor\sqrt[3]{a}\rfloor$ 时，$y^3 \leq a$，很明显在 $a$ 不是完全立方数时满足 $y^3 < a$，例如 $a = 3$ 时，$y = \lfloor\sqrt[3]{3}\rfloor = 1$，而 $y^3 = 1 < a$。

接着我们考虑在区间 $[\lceil\sqrt[3]{a}\rceil, \lfloor\sqrt[3]{b}\rfloor]$ 之间枚举 $y$。这时 $|x^2 - y^3| \leq k$ 就可以看成 $x^2$ 只能在 $[y^3 - k, y^3 + k]$ 中。那么当 $y^3 - k \geq 0$ 时，$x$ 的最小取值为 $\sqrt{y^3 - k}$，当 $y^3 - k < 0$ 时，我们让 $x = 0$。

所以，$x$ 所在的区间也就是 $[\sqrt{\max\{0, y^3 - k\}}, \sqrt{y^3 + k}]$。但是题目要求 $a\leq x^2 \leq b$，所以最终 $x$ 的取值范围就是 $[\sqrt{\max\{y^3 - k, a\}}, \sqrt{\min\{y^3 + k, b\}}]$。我们都知道 $l\sim r$ 之间的整数的个数为 $r - l + 1$，那么我们就可以解出这道题了。

算法总时间复杂度 $\mathcal{O}(\sqrt[3]{b - a})$。

CODE：

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
	ios::sync_with_stdio(false);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int a, b, k, ans = 0;
	cin >> a >> b >> k;
	int l = ceil(cbrt(a)), r = cbrt(b);
	for (int y = l; y <= r; y++) {
		ans += floor(sqrt(min(y * y * y + k, b))) - ceil(sqrt(max(y * y * y - k, a))) + 1;
	}
	cout << ans;
	return 0;
}