【ABC166】D - I hate Factorizationの理解

atcoder.jp

全探索で解ける問題だが、どこからどこまで全探索するかを考える必要がある問題。

公式解説読んでピンと来なかったので、僕でも理解できるように丁寧に追いかけてみた（嘘だったら教えてください）。

---

まず、制約から 1 <= x <= 10⁹ であり、 x == A⁵ - B⁵ になるA, Bを探すので、単純に 1 <= A⁵ - B⁵<= 10⁹ の範囲を調べたら十分そうである。

この上で、1 <= A⁵ - B⁵ <= 10⁹ のとき、AとBにどんな数字が入るか考える。

A == B であることはなさそう。A == B なら A⁵ == B⁵なので、A⁵ - B⁵ == 0 になる。xは0ではない（1以上）ので、この状況はありえない。

さらに 1 <= A⁵ - B⁵<= 10⁹ なので、A⁵ - B⁵ がマイナスになることはない、つまり A > B と考えて良さそうである。

ここまでで、AとBは異なる整数であり、Aのほうが大きいということが分かる。例えば A == n とするなら、0 <= B <= |n-1| になりそうである。

---

A == n 、0 <= B <= |n-1| とすると、例えば n⁵ - 1⁵ より、n⁵ - (n-1)⁵ のほうが小さい数になるし、n⁵ - 1⁵ と n⁵ - (n-1)⁵ で同じくらいの大きさの数を作ろうとするとnの絶対値がより大きい数になるのはn⁵ - (n-1)⁵の方である。

なので、1<= n⁵ - (n-1)⁵ <= x のときnがどんな数字をとるのか確かめれば、AとBを最大でどこからどこまで全探索すればいいかわかりそうである。

ここからは公式解説に載っているし計算すればわかるが、-118 <= A <= 119、-199 <= B <= 118 を調べれば良いらしい。

つまり、1 <= A⁵ - B⁵<= 10⁹ のとき、-118 <= A <= 119、-199 <= B <= 118 であり、また問題文から、今回はこの中にxが存在することが保証されている。

https://img.atcoder.jp/abc166/editorial.pdf

---

簡単に計算するとは言ったものの、10⁹超えてくるまで n⁵ - (n-1)⁵ を計算するのは面倒だと思うので、計算するためだけにこんな感じにプログラムを組めば確かめられる気がする。

x = 10**9
n = 1
while n**5 - (n-1)**5 < x:
    n += 1
n -= 1
# max A: 119 , max B: 118
print('max A:', n, ', max B:', n-1)
n = -1
while n**5 - (n-1)**5 < x:
    n -= 1
n += 1
# min A: -118 , min B: -119
print('min A:', n, ', max B:', n-1)

---

これで多分 10² * 10² = 10⁴ くらいで求められる。

ただしこの考えだと結構計算量に余裕がありそうだし、ここまでコンテスト中に考えるのは大変なので、本番でここまで考察できなくても、もうちょっとざっくり当たりをつけて全探索しても解けるらしい。