d188: 11342 - Three-square
Tags :
Accepted rate : 205人/252人 ( 81% ) [非即時]
評分方式:
Tolerant

最近更新 : 2009-04-23 18:08

Content

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

3 = 12 + 12 + 12 + 02
31 = 52 + 22 + 12 + 12

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

3 = 12 + 12 + 12
17 = 02 + 12 + 42

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

Input
第一行有一個整數 N (0 < N <= 10000),表示有幾個測試資料。接下來的 N 行每行有一個正整數 K (0 < K <= 50000)。
Output
對於每一個測資,請以 "a b c" 的格式印出一行。其中 a <= b <= c 且 K = a2 + b2 + c2。如果可能的答案不只一個,印出字典順序最小的。如果無法以三個非負平方數來表示則印 "-1" (參考範例)。
Sample Input
3
13
15
17
Sample Output
0 2 3
-1
0 1 4
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :
Tags:
出處:
UVa11342 [管理者:
snail (蝸牛)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」