主題
題目連結：
題目意譯：
給定一個非負整數 c，判斷是否存在兩整數 a 和 b 使得 a ^ 2 + b ^ 2 = c。
限制：
0 ≦ c ≦ 2 ^ 31 - 1
範例測資：
範例 1：
輸入： c = 5
輸出： true
解釋： 1 × 1 + 2 × 2 = 5
範例 2：
輸入： c = 3
輸出： false
範例 3：
輸入： c = 4
輸出： true
範例 4：
輸入： c = 2
輸出： true
範例 5：
輸入： c = 1
輸出： true
解題思維：
根據費馬平方和定理（Fermat's Theorem on Sums of Two Squares），所有形為 4n + 1（換句話說，模 4 後的餘數為 1）之質數 p 必能表為兩平方數之和，即存在兩數 a 、 b 滿足 a ^ 2 + b ^ 2 = p。
而再根據婆羅摩笈多-斐波那契恆等式（Brahmagupta–Fibonacci Identity），如果有兩數 x 、 y 各自都可表為兩平方數之和，則其乘積 xy 也可被表為兩平方數之和。
假設給定的目標數字 c 的質因數分解為
P1 ^ C1 × P2 ^ C2 × ……
其中 P1 、 P2 、……皆是質數，而 C1 、 C2 、…… 皆大於 0。
而當 P1 、 P2 、……都可被表為平方數之和（根據費馬平方和定理），且 C1 、 C2 、…… 皆為偶數，則根據婆羅摩笈多-斐波那契恆等式便可以知道目標數字 c 可表為兩平方數之和；反之有任何一個條件不符合，則 c 無法表為兩平方數之和。
至於質因數分解的方式可以參見這題。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
