AtCoder　ABC.166　D問題「I hate Factorization」見直し

解説みてどうにか、こうにかですね。

問題

A^5−B^5=Xを満たす整数の組 (A,B)をひとつ示してください。 ただし、与えられるXに対して、条件を満たす整数の組 (A,B)が存在することが保証されています。

条件

1≦X≦10^9
Xは整数

解答例

n = int(input())

a = [i**5 for i in range(120)]
for i in range(120):
   for j in range(i+1,120):
       if a[j]-a[i] == n:
           print(j,i)
           break
       if a[j]+a[i] == n:
           print(j,-i)
           break
   else: continue
   break

反省

なんで、上記が出なかったのか。一番大きな要因はAとBが取りうる最大値を考えることができなかったことだろう。AとBの取りうる最大値は、AとBの差が最小（1）の場合「n^5-(n-1)^5」で回答が10^9を超える値を算出することで求められる。

#+の場合
i = 0
ans = 0
while ans <= 1000000000:
   i += 1
   ans = i**5 - (i-1)**5
print(i)#120

#-の場合
i = 0
ans = 0
while ans <= 1000000000:
   i -= 1
   ans = i**5 - (i-1)**5 
print(i)#-119

ということで、それ以上だと差が10^9に収まらないためAとBが取りうる最大の値は119ということになる。（ちなみに差が2の場合は差がさらに大きくなるので101とかになる。）

ここまで考えられたらあとは結構簡単で、「1^5,2^5,3^5,4^5,.....119^5」のリストを作成して、総当たりで回答を求めると良い。ちょっと気にしないといけないのは、Bの値が「-(マイナス)」の場合も忘れない様にすること。

いやぁ、次似た問題が出たら回答したいな。