四平方和

原題目鏈接

題目描述

四平方和定理（又稱拉格朗日定理）指出：

每個正整數都可以表示為 至多 4 個正整數的平方和。

如果將 0 包括進去，則每個正整數都可以恰好表示為 4 個非負整數的平方和。

例如：

• 5 = 02 + 02 + 12 + 22
• 7 = 12 + 12 + 12 + 22

對于一個給定的正整數，可能存在多種平方和表示法。

本題要求你對所有可能的表示法滿足以下排序條件：

• 四個數滿足 0 ≤ a ≤ b ≤ c ≤ d
• 對所有可能的 (a, b, c, d) 按照字典序（即聯合主鍵）升序排列，輸出第一個表示法。

---

輸入描述

輸入一個正整數 N（N < 5 × 10?）。

---

輸出描述

輸出一組符合條件的 4 個非負整數 (a b c d)，中間用空格隔開，滿足：

• a2 + b2 + c2 + d2 = N
• 0 ≤ a ≤ b ≤ c ≤ d
• 為所有合法組合中字典序最小的一組

---

輸入樣例

12

---

輸出樣例

0 2 2 2

c++代碼

#include<bits/stdc++.h>using namespace std;int main() {int N, m;cin >> N;for (int i = 0; i * i <= N; i++) {for (int j = 0; i * i + j * j <= N; j++) {for (int k = 0; i * i + j * j + k * k <= N; k++) {int res = N - i * i - j * j - k * k, m = (int)sqrt(res);if (m * m == res) {cout << i << " " << j << " " << k << " " << m;return 0;}}}}return 0;
}//by wqs