P11177 [ROIR 2018 Day1] 平方与立方 题解

· · 题解

通俗题意

给你三个整数 a, b, 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;
}