算法學習之路|四平方和

題目大意

四平方和定理，又稱為拉格朗日定理：每個正整數都可以表示為至多 4 個正整數的平方和。如果把 0包括進去，就正好可以表示為 4 個數的平方和。

比如：

5=0^2+0^2+1^2+2^2

7=1^2+1^2+1^2+2^2

則對于一個給定的正整數 n，可以表示為：n=a^2+b^2+c^2+d……。

你需要求出字典序最小的一組解 a,b,c,d。

字典序大小：從左到右依次比較，如果相同則比較下一項，直到有一項不同，較小的一方字典序更小，反之字典序更大，所有項均相同則二者字典序相同。

輸入格式

程式輸入為一個正整數 N(1≤N≤5000000)。

輸出格式

輸出 4個非負整數 a,b,c,d中間用空格分開。

樣例輸入1

5

樣例輸出1

0 0 1 2

樣例輸入2

12

樣例輸出2

0 2 2 2

其實我們隻需要枚舉 a,b,ca,b,c 就可以了，因為 dd 是可以通過 a,b,c

a,b,c 的值計算出來的。這樣我們就可以減少一層循環，進而降低程式運作時間，以避免運作逾時。