题解：AT_abc397_d [ABC397D] Cubes

· · 题解

题目简述

给定正整数 N，判断是否存在 x 与 y 使得 x^{3}-y^{3}=N。

主要思路

数学题。x^{3}-y^{3} 通过立方差公式可得：

(x-y)(x^{2}+xy+y^{2})

设正整数 z=x-y，为了满足 (x-y)(x^{2}+xy+y^{2})=n，所以 z 为 n 的因数，将 x=y+z 代入：

z[(y+z)^{2}+(y+z)y+y^{2}]=z(y^{2}+2yz+z^{2}+y^{2}+yz+y^{2})=z(3y^{2}+3yz+z^{2})

得到方程：

z(3y^{2}+3yz+z^{2})=n

再得到：

3y^{2}+3yz+(z^{2}-\frac{n}{z})=0

此时使用判别式为：

\Delta = (3z)^{2}-4\cdot3\cdot(z^{2}-\frac{n}{z})=9z^{2}-12z^{2}+\frac{12n}{z}=-3z^{2}+\frac{12n}{z}

那么

y=\frac{-3z+\sqrt{\Delta}}{6}

为了使 y 为正整数，\Delta 一定为非负的完全平方数。即

-3z^{2}+\frac{12n}{z}\ge0\Rightarrow \frac{12n}{z}\ge3z^{2}\Rightarrow 4n\ge z^{3}

接下来就可以开始枚举 z 了，刚才得到 4n\ge z^{3}，所以枚举直到 z^{3}>4n，接下来判断

  2. 判断 \Delta 是否为非负的完全平方数。
  3. 判断 y 是否为正整数。

以上条件都满足，则称为找到了一组 x 与 y，x=y+z，立即输出并结束程序即可。

如果枚举完所有的 z 后仍没有找到合适的答案，则输出 -1。

注：这种写法本题会炸 long long，但开 unsigned long long 即可。

AC Code

#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long double db;
typedef unsigned long long ll;
const int INT_INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
// ----------------------------

// ----------------------------

// ----------------------------

int main() {
    ll n; cin >> n;
    // ----------------------------
    ll d, s, y, x;
    for (ll z = 1; z * z * z <= n * 4; z++) {
        if (n % z != 0) continue;
        d = -3 * z * z + 12 * (n / z);
        if (d < 0) continue;
        s = sqrt(d);
        if (s * s != d) continue;
        y = (-3 * z + s) / 6;
        if (y <= 0) continue;
        x = y + z;
        cout << x << ' ' << y;
        return 0;
    }
    // ----------------------------
    cout << -1;
    return 0;
}