轉載請註明出處：http://www.cnblogs.com/zhishoumuguinian/p/8372337.html 四平方和定理，又稱為拉格朗日定理：每個正整數都可以表示為至多4個正整數的平方和。如果把0包括進去，就正好可以表示為4個數的平方和。比如：5 = 0^2 + 0^2 + 1^2 ...
轉載請註明出處：http://www.cnblogs.com/zhishoumuguinian/p/8372337.html
四平方和定理，又稱為拉格朗日定理：每個正整數都可以表示為至多4個正整數的平方和。如果把0包括進去，就正好可以表示為4個數的平方和。比如：5 = 0^2 + 0^2 + 1^2 + 2^2 7 = 1^2 + 1^2 + 1^2 + 2^2 （^符號表示乘方的意思）對於一個給定的正整數，可存在多種平方和的表示法。要求你對4個數排序：0 <= a <= b <= c <= d。並對所有的可能表示法按 a,b,c,d 為聯合主鍵升序排列，最後輸出第一個表示法。程式輸入為一個正整數N (N<5000000)，要求輸出4個非負整數，按從小到大排序，中間用空格分開
例如，輸入：
5
則程式應該輸出：
0 0 1 2
再例如，輸入：
12
則程式應該輸出：
0 2 2 2
再例如，輸入：
773535
則程式應該輸出：
1 1 267 838
資源約定：
峰值記憶體消耗 < 256M
CPU消耗 < 3000ms
請嚴格按要求輸出，不要畫蛇添足地列印類似：“請您輸入...” 的多餘內容。所有代碼放在同一個源文件中，調試通過後，拷貝提交該源碼。
註意: main函數需要返回0
註意: 只使用ANSI C/ANSI C++ 標準，不要調用依賴於編譯環境或操作系統的特殊函數。
註意: 所有依賴的函數必須明確地在源文件中 #include <xxx>， 不能通過工程設置而省略常用頭文件。
提交時，註意選擇所期望的編譯器類型。
思路：四個數的平放，第一想法是四層迴圈，但是最後一層循可以省略。每層迴圈到sqrt（5000000）+1即可，可以先輸出一下，sqrt（5000000）+1值為2237。大題思路就是這樣，接下來粘上代碼。
1 #include <iostream>
2 #include <cmath>
3 using namespace std;
4
5
6 int main()
7 {
8 int n;
9 cin>>n;
10 //n=5000000;
11 for(int a=0; a<=2237; a++)
12 {
13 for(int b=0; b<=2237; b++)
14 {
15 for(int c=0; c<=2237; c++)
16 {
17 int dj=n-a*a-b*b-c*c;
18 int d=sqrt(dj);
19 if(dj==d*d)//如果dj等於d的平方，第四位數是一個整數的平方，這個整數d就是第四位數
20 {
21 cout<<a<<" "<<b<<" "<<c<<" "<<d;
22 return 0;
23 }
24 }
25 }
26 }
27 }
題目限制時間是3秒
計算的5000000，DEV-C++執行時間 CODEBLOCKS執行時間
如果本文對你有幫助，請給個
