【ABC166 D】「I hate Factorization」を解く【Python3】

「A⁵−B⁵=X」を満たす整数の組(A,B)をひとつ示す問題です。

提出

x = int(input())
 
for a in range(1, 120):
    for b in range(-119, 119):
        if a**5-b**5 == x:
            print(a, b)
            exit()

可能性のあるA,Bを全探索することで、解いていきます。

Xが正の整数だということを考えると、「A>0」と「A<0」のどちらも可能性としてはあり得るのですが、片方の「A>0」のみを調べるだけでも、答えを導くことができます。

仮に、「A=-3, B=-5」だった場合、「A⁵−B⁵=2882」となりますが、

これは「A=5, B=3」だった場合と等しいです。

また、Bが正の整数だった場合は、Aは必ず正の整数になります。

このことから「A>0」の範囲を調べれば済むことがわかります。

最大は「A=119, B=118」になります。

「A=120, B=119」の場合にXが「10⁹」を超えるので、それ以上は考えなくて良いためです。

A,Bの差が大きいと、「A⁵−B⁵」が大きくなるので、探索すればいい範囲は狭まります。

Bの最小値は「-119」で問題ないです。

（Bが負の場合は、「|B⁵|>10⁹」の範囲を考える必要がないので、これより狭めることもできます）

【ABC166】解説記事リスト