問題概要

非負整数 $a, b$ を用いて

$X = a^{3} + a^{2}b + a b^{2} + b^{3}$

と表せる整数 $X$ を「特別数」と呼ぶことにします。

非負整数 $N$ が与えられますので、 $N$ 以上である最小の「特別数」を求めてください。

制約

$0 \le N \le 10^{18}$

変数が複数あるときは 1 つを固定する

見た目は確かに数学色の強い問題だけど、考えるべき基礎は決して特別なものではない。

このように $a, b$ という 2 つの変数が絡む問題で考えるべきことは、1 つの変数を固定して考えるというもの。

ここでは $a$ を固定してみよう。たとえば $a = 5$ としたとしてみよう。このとき、

$X = b^{3} + 5 b^{2} + 25 b + 125$

となる。これが $N$ 以上となるような最小の $b$ を求めたいと思ったら、それはまさに二分探索法がどんぴしゃだ！！

つまり次のように求められる。

// 式計算
long long func(long long a, long long b) {
    return a*a*a + a*a*b + a*b*b + b*b*b;
}

// a を固定したときの N 以上の最小の特別数を求める
long long solve(long long a) {
    long long low = -1, high = (十分大きな値);
    while (high - low > 1) {
        long long b = (low + high) / 2;
        if (func(a, b) >= N) high = b;
        else low = b;
    }
    return func(a, high);
}

変数の範囲を考える

最後に検討すべきことは以下の 2 点だ

変数 $a$ の調べるべき範囲
変数 $a$ を固定したとき、二分探索法の初期値の決め方

これを考える前に、 $X = 10^{18}$ が「特別数」であることを確認しよう。具体的には $a = 10^{6}$ , $b = 0$ としたとき

$a^{3} + a^{2} b + a b^{2} + b^{3} = 10^{18}$

となるのだ。よって $N \le 10^{18}$ という制約を考えると、 $N$ 以上の最小の特別数が $10^{18}$ より大きくなる可能性は考えなくて良いのだ！！！

そのことから、 $a \gt 10^{6}$ の範囲を調べる必要がないことが言える。なぜなら $a \gt 10^{6}$ とすると

$a^{3} + a^{2} b + a b^{2} + b^{3} \ge a^{3} \gt 10^{18}$

となるためだ。 $10^{18}$ より大きくなる範囲は考慮不要なので、 $a \gt 10^{6}$ は考えなくてよい。

同様に $a$ を固定したとき、 $a^{3} + a^{2} b + a b^{2} + b^{3}$ が $N$ 以上となる最小の $b$ を求めるための二分探索法の上限値も、 $10^{6}$ より大きく取る必要はない！！

以上より、次の結論が言える

変数 $a$ は $0, 1, 2, \dots, 10^{6}$ まで調べれば十分
変数 $a$ を固定したとき、二分探索法の上限値の初期値は $10^{6}$ とすればよい

計算時間的にも十分に間に合う。一応計算量をちゃんと書くと、 $O(N^{\frac{1}{3}} \log N)$ と評価できる。

コード

#include <bits/stdc++.h>
using namespace std;

long long func(long long a, long long b) {
    return a*a*a + a*a*b + a*b*b + b*b*b;
}

long long solve(long long N, long long a) {
    long long low = -1, high = 1000000;
    while (high - low > 1) {
        long long b = (low + high) / 2;
        if (func(a, b) >= N) high = b;
        else low = b;
    }
    return func(a, high);
}

int main() {
    long long N;
    cin >> N;

    long long res = 1000000000000000000LL;  // 10^18 が上限値
    for (long long a = 0; a <= 1000000; ++a) {
        res = min(res, solve(N, a));
    }
    cout << res << endl;
}