AtCoder Beginner Contest D - Cubes 题解

题目大意

给定一个正整数 $N$，如果存在正整数 $x,y$ 满足 $x^3 - y^3 = N$，那么输出 $x, y$，否则输出 $-1$.

分析

考虑枚举，由于式中出现了减法，因此上界会很大，不便于枚举.

具体地，在本题条件下，若令 $y = x -1$，则 $N = x^3 - (x-1)^3 = 3x^2 -3x + 1$，也即 $x,y$ 可以达到 $\sqrt N$ 的级别.

于是考虑变形，有

$x^3 - y^3 = (x - y)(x^2 +xy + y^2)$

我们令 $k = x - y$，将减法部分整体换元，于是有

$\begin{aligned} x^3 - y^3 &= (x - y)(x^2 +xy + y^2) \\ &= (x - y)[(x - y)^2 + 3xy] \\ &= k[k^2 + 3y(y + k)] \\ \end{aligned}$

此时式中只含加法，容易发现 $N = x^3 - y^3 = k[k^2 + 3y(y + k)] > k^3$，因此 $1 \le k < \sqrt[3]N$，于是我们可以枚举 $k$.

考虑到 $k$ 已经确定，对原式进行变形

$\begin{aligned} k[k^2 + 3y(y + k)] &= N \\ k^2 + 3y(y + k) &= \frac{N}{k} \\ 3y^2 + 3ky + k^2 &= \frac{N}{k} \\ 3y^2 + 3ky + k^2 - \frac{N}{k} &= 0 \\ \end{aligned}$

这是一个关于 $y$ 的二次方程，使用求根公式对其进行求解

$\begin{aligned} & a = 3, b = 3k, c = k^2 - \frac{N}{k} \\ & \Delta = b^2 - 4ac \\ & y_1 = \frac{-b - \sqrt\Delta}{2a}, y_2 = \frac{-b + \sqrt\Delta}{2a} \\ \end{aligned}$

其中显然 $y_1 < 0$，因此只考虑 $y_2$.

若解出 $y_2$ 为合法的解，输出 $x = y_2 + k, y = y_2$ 即可.

代码

#include <bits/stdc++.h>

using namespace std;

using ULL = unsigned long long;

ULL n;

int main() {
    cin >> n;
    for(ULL k = 1; k * k * k < n; k++) {
        ULL a = 3, b = 3 * k, c = k * k - n / k, 
            delta = b * b - 4 * a * c, sq = sqrt(delta * 1.0L),
            y = (-b + sq) / (2 * a),
            res = k * (k * k + 3 * y * (y + k));
        if(res == n)
            cout << y + k << " " << y << "\n", exit(0);
    }
    cout << -1;
    return 0;
}

容易证明，该代码的时间复杂度为 $\mathrm O(\sqrt[3]N)$.

一些细节

算法实现

值得注意的是，当 $k = 1$时，$\Delta = 9 - 12(1^2-N) = 12N - 3$ 可能会超出 long long 类型的存储范围，但不超出 unsigned long long 类型的存储范围（认为其均为 $64$ 位整型），因此应当使用 unsigned long long 类型存储和运算.

另外，容易得到 $\displaystyle \Delta = 3k^2(\frac{4N}{k^3} - 1) > 0$，因此不需要考虑方程无解的情况.
同时，$\displaystyle -b + \sqrt\Delta = \sqrt{3k^2(\frac{4N}{k^3} - 1)} - 3k = 3k(\sqrt{\frac{N}{k}+\frac{N-k^3}{k^3}} - 1) > 0$，即 $y_2 > 0$，因此也不用考虑 $y$ 非正的情况.

时间优化

由 $N = x^3 - y^3 = k[k^2 + 3y(y + k)]$ 易知，$k$ 必为 $N$ 的因数，但由于求小于$\sqrt[3]N$因数依然可以到到 $\mathrm O(\sqrt[3]N)$，因此没有实现的必要.
不过，通过通过在 $k \nmid N$ 时跳过该次循环，可以大幅减小常数，但是由于单词循环是 $\mathrm O(1)$ 的，因此时间复杂度没有改变.