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

コンテスト一覧へ

 

「A5−B5=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」だった場合、「A5−B5=2882」となりますが、

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

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

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

 

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

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

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

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

(Bが負の場合は、「|B5|>109」の範囲を考える必要がないので、これより狭めることもできます)

【ABC166】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。