以下、 \(f(a,b)=a^3+a^2b+ab^2+b^3\) とします。

まず、 \(N \le 10^{18}\) であるので、 \(f(a,b)\) が答えとなるとき \(a,b \le 10^6\) であることが分かります。( \(f(10^6,0)=10^{18}\) であり、もし \(a,b\) の少なくとも一方が \(10^6\) より大きいなら \(f(a,b)>10^{18}\) となります。)

なので、この問題での目標は、全ての \(0 \le i \le 10^6\) に対して \(f(i,j) \ge N\) なる最小の非負整数 \(j\) を求め、それら全てに対して \(\min f(i,j)\) を求めることになります。

ここで、 \(i_1 \le i_2\) であるとき、 \(i=i_1\) である場合の \(j\) を \(j_1\) 、 \(i=i_2\) である場合の \(j\) を \(j_2\) とすると、 \(j_1 \ge j_2\) となります。 (\(f(i_1,j_1) \ge N\) のとき、\(f(i_2,j_1) \ge N\) となります。)

この性質を利用して、以下のアルゴリズムが成立します。

• はじめ、変数 \(j=10^6\) と初期化する。また、暫定的な解 \(X= \infty\) としておく。
• \(i = 0\) から \(10^6\) まで、以下を繰り返す。
  • \(f(i,j) \ge N\) かつ \(j \ge 0\) である限り、以下を繰り返す。
    • \(X=\min(X,f(i,j))\) とし、その後 \(j\) を \(1\) 減算する。

実装例(C++):

#include<bits/stdc++.h>

using namespace std;

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

int main(){
  long long n;
  cin >> n;
  long long x=8e18;
  long long j=1000000;
  for(long long i=0;i<=1000000;i++){
    while(f(i,j)>=n && j>=0){
      x=min(x,f(i,j));
      j--;
    }
  }
  cout << x << '\n';
  return 0;
}

また、このアルゴリズムと同等のことを以下のように実装すると定数倍高速です。この実装は、本質的には尺取り法です。

実装例(C++):

#include<bits/stdc++.h>

using namespace std;

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

int main(){
  long long n;
  cin >> n;
  long long x=8e18;
  long long i=0,j=1000000;
  while(i<=j){
    long long cf=f(i,j);
    if(cf>=n){x=min(x,cf);j--;}
    else{i++;}
  }
  cout << x << '\n';
  return 0;
}