[ABC246] D - 2-variable Function
[Q] https://atcoder.jp/contests/abc246/tasks/abc246_d
1. a <= b で考える。
2. bは∛N以下までしかこない。
3. f(0, ∛N) からスタート。しゃくとりする。
(a) もしf() < Nなら、(a+1, b) に遷移。
(b) もしf() >= N なら、min(ans)の更新をし、(a, b-1) に遷移。
N = 1010 を考える。
1. bは3乗根からスタート。
N ≒ 10 * 10 * 10
a=0, b=10+1 からスタート
3.
f(0, 11) = 1331 >= 1010 なので、b-1, ans = 1331
f(0, 10) = 1000 < 1010 なので、a+1
f(1, 10) = 1111 >= 1010 なので、b-1, ans = 1111
f(1, 9) = 820 < 1010 なので、a+1
f(2, 9) = 935 < 1010 なので、a+1
f(3, 9) = 1080 >= 1010 なので、b-1, ans = 1080
...
ans = 1080実装
ll f(ll a, ll b) { return a * a * a + a * a * b + a * b * b + b * b * b; }
int main() {
cincout();
ll N;
cin >> N;
if (N == 0) {
cout << 0 << endl;
return 0;
}
ll ans = oo;
ll head = 0;
ll tail = cbrtl(N) + 1;
while (tail >= head) {
ll now = f(head, tail);
if (now < N)
++head;
else {
chmin(ans, now);
--tail;
}
}
cout << ans << endl;
}