高中生程式解題系統d188: 11342 - Three-square－資工趴趴熊的小天地

Content

根據 Lagrange 的四平方和定理，每個正整數可以用四個完全平方數的和來表示。例如：

3 = 1² + 1² + 1² + 0²
31 = 5² + 2² + 1² + 1²

可是有些正整數可以用三個非負完全平方數的和來表示。例如：

3 = 1² + 1² + 1²
17 = 0² + 1² + 4²

給你一個整數 K 請你以三個平方數的和來表示，或是陳明這是不可能的。

Input

第一行有一個整數 N (0 < N <= 10000)，表示有幾個測試資料。接下來的 N 行每行有一個正整數 K (0 < K <= 50000)。

Output

對於每一個測資，請以 "a b c" 的格式印出一行。其中 a <= b <= c 且 K = a² + b² + c²。如果可能的答案不只一個，印出字典順序最小的。如果無法以三個非負平方數來表示則印 "-1" (參考範例)。

Sample Input #1

t=int(input())
strn=[-1]*50001
for i in range(255):
    for j in range(i,255):
        for k in range(j,255):
            if((i*i+j*j+k*k)>50000): break
            if(strn[i*i+j*j+k*k]==-1): strn[i*i+j*j+k*k]=(str(i)+" "+str(j)+" "+str(k))
for z in range(t):
    ans=int(input())
    print(strn[ans])

Sample Output #1

0 2 3
-1
0 1 4

python TLE版:

strn=[-1]*50001
for i in range(255):
  for j in range(255):
    for k in range(255):
      if(i**2+j**2+k**2)>50000:break
      if strn[i**2+j**2+k**2]==-1:strn[i**2+j**2+k**2]=str(i)+' '+str(j)+' '+str(k)
#print(strn)
t=int(input())
for i in range(t):
  ans=int(input())
  print(strn[ans])

python AC版:

t=int(input())
strn=[-1]*50001
for i in range(255):
    for j in range(i,255):
        for k in range(j,255):
            if((i*i+j*j+k*k)>50000): break
            if(strn[i*i+j*j+k*k]==-1): strn[i*i+j*j+k*k]=(str(i)+" "+str(j)+" "+str(k))
for z in range(t):
    ans=int(input())
    print(strn[ans])