\(\mathrm{O}(\sqrt{N})\) 解法

制約より、\(N >0\) です。よって、\(x^3-y^3=N\) を満たすような \((x,y)\) について、 \(y+1 \leq x\) が成り立ち、\((y+1)^3-y^3=3y^2 +3y+1 \leq x^3-y^3 =N\) です。つまり、\(y \leq \sqrt{N}\) が成り立ちます。

よって、\(1\) 以上 \(\sqrt{N}\) 以下の整数 \(k\) を全探索し、\(k^3+N\) が立法数であるか判定し、立法数である場合は \((x,y)=(\sqrt[3]{k^3+N},k)\) が解の一つとなります。

逆に、上を満たすような \(k\) が存在しなければ、解は存在しません。

以上より、時間計算量 \(\mathrm{O}(\sqrt{N})\) で解くことができます。ですが、この解法では今回の制約ではACを得ることは難しいです。

\(\mathrm{O}({\sqrt[3]{N}})\) 解法

\(x-y=d\) とします。 \(x^3-y^3=N\) を満たすような \((x,y)\) について、\(x^3-y^3=(x-y) (x^2+xy+y^2)=d(x^2+xy+y^2)\) です。また、\(x^2+xy+y^2 \geq x^2-2xy+y^2 =d^2\) より、\(d^3 \leq d(x^2+xy+y^2) = x^3-y^3 =N\) を満たします。

つまり、\(d \leq \sqrt[3]{N}\) を満たします。

よって、\(1\) 以上 \(\sqrt[3]{N}\) 以下の整数 \(d\) を全探索し、\((k+d)^3-k^3=d^3+3d^2 k+3dk^2=N\) を満たす整数 \(k\) が存在するか判定し、ある場合は\((x,y)=(k+d,k)\) が解の一つとなります。

逆に、上を満たすような \(d\) が存在しなければ、解は存在しません。

\(d\) が与えられたとき、\(d^3+3d^2 k+3dk^2=N\) を満たす\(k\) を求めるのは\(3dk^2+3d^2k+d^3-N=0\) と変形し、この二次方程式を解くことで求められます。今回の場合、これは二次方程式の解の公式や二分探索を用いることで解けます。

以上より時間計算量 \(\mathrm{O}(\sqrt[3]{N})\) や \(\mathrm{O}(\sqrt[3]{N}\log N)\) などで解くことができます。

また、実装の際はオーバーフローに気を付ける必要があります。 特に、二次方程式の解を求めるとき、直接解の公式で求めるとオーバーフローすることがあります。適切な実装の下で二分探索を用いるとオーバーフローしません。

実装例 \((\mathrm{O}(\sqrt[3]{N}\log N))\)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll sol(ll a, ll b, ll c) {
    // ax^2 + bx + c = 0の解
    ll l = 0, r = 600000001;
    while (r - l > 1) {
        ll mid = (l + r) / 2;
        if (a * mid * mid + b * mid + c <= 0)
            l = mid;
        else
            r = mid;
    }
    if (a * l * l + b * l + c == 0)
        return l;
    return -1;
}
int main() {
    ll n;
    cin >> n;
    for (ll d = 1; d * d * d <= n; ++d) {
        // (k+d)^3 - k^3 = d^3 + 3*d^2k + 3*d*k^2 = n
        if (n % d != 0)
            continue;
        ll m = n / d; // =3*k^2 + 3*dk + d^2
        ll k = sol(3, 3 * d, d * d - m);
        if (k > 0) {
            cout << k + d << " " << k << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}