ABC246-D問題にて、探索範囲がなぜ決まるのか分からない。

Question

前提

ABC246-Dを解いている過程で、制約的にaを10^6まで全探索かつ、bを二部探索するだろうと思いましたが、なぜそうなるのかわかりません。
解説を見てみると実際その解法でした。

分からない点

0≤N≤10^18
N≤Xなので、Xは10^18よりも大きくなる場合があると思います。
なのになぜ、aとbの制約を10^6までに決定することができるのかわかりません。
a = b = 10^6 まで調べても条件を満たすXを見つけることが保証されているのでしょうか？

Comments

[Zuishin]

公式以外の解説を検索してみるといいんじゃないかと思います。
公式解説が間違っているなら間違っている旨が、正しいならその意図がみつかると期待できます。
たとえば、以下のページなど。
https://drken1215.hatenablog.com/entry/2022/04/03/144800

Answer 1

(説明が分かりにくかったらすみません...)

• XはN以上である
• X=a³+a²b+ab²+b³ を満たす非負整数(a, b)の組が存在する

上の条件をすべて満たす整数Xのうち、最小のものを求めよ

まずは一旦「条件を満たす整数Xのうち最小のもの」という文を無視した上で、Nに具体的な数値を当てはめてみましょう。

• N=10¹⁸のときは、もちろんX=10¹⁸が条件を満たします。
• N=10¹⁸-1=9999...9999 のときも、X=10¹⁸はN≦Xなので条件を満たします。
• N=10¹⁸-2=9999...9998 のときも、X=10¹⁸は条件を満たします。
• …(以下略)

このように考えると、N=0, 1, 2, ..., 10¹⁸のどの場合でも、X=10¹⁸は条件を満たすことが分かりますね。

そして、無視していた文をもう一度含めて考えると、0≦N≦10¹⁸ならば、

• 「条件を満たす整数Xのうち最小のもの」は、どんなに大きくても必ず10¹⁸以下になる

ことが分かります。
(もし「最小のもの」が10¹⁸より大きいなら、X=10¹⁸は条件を満たさないことになってしまいます)

したがって、(最小の整数X)≦10¹⁸であり、a, bの範囲を a≦10⁶かつb≦10⁶ と絞り込めるというわけです。

Answer 2

保証されています。というか、そもそもXを見つける問題じゃなくて(a,b)を見つける話なので。（(a,b)を決めればXは計算で出る）
a=10^6なら、Xの最小は(a,b)=(10^6,0)のペアのときで、Xは10^18になって、Nmax<=Xを満たします。
当然、a,bがそれ以上のときにNmax<=Xを満たすのも自明だけど、最小が欲しいわけだから探しても無駄。