AtCoder Beginner Contest 246 D問題 2-variable Function

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

以下を満たす最小の整数 $X$ を求めよ.

$X \geq N$
$X=a^3+a^2 b+a b^2+b^3$ を満たす非負整数 $a,b$ が存在する.

制約

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

解法

$N$ に対する答えを $X(N)$ と書くことにし, $f(a,b):=a^3+a^2 b+a b^2+b^3$ とする.

そして, $f(0,10^6)=10^{18}$ であり, $N \leq 10^{18}$ という制約から, $X(N) \leq 10^{18}$ である. また, $b \gt 10^6$ ならば, $f(a,b) \gt 10^{18}$ である. よって, $M:=10^6$ として, $b \leq M$ の各 $b$ について $\displaystyle \min_{f(a,b) \geq N} f(a,b)$ を調べれば良い.

$0 \leq b \leq M$ となる整数 $b$ を1つ固定する. このとき, $g_b(a):=f(a,b)$ とすると, $g_b$ は単調増加である. よって, $g_b(a) \geq N$ を満たす最小の非負整数を $a(b)$ と書くことにすると, $\displaystyle \min_{f(a,b) \geq N} f(a,b)=g_b(a(b))$ である.

従って,

$\displaystyle X(N)=\min_{f(a,b) \geq N} f(a,b)=\min_{0 \leq b \leq M} \left(\min_{\substack{f(a,b) \geq N}} f(a,b) \right)=\min_{0 \leq b \leq M} g_b(a(b))$