題目

四平方和定理，又稱為拉格朗日定理：
每個正整數都可以表示為至多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 ， 不能通過工程設置而省略常用頭文件。

提交時，注意選擇所期望的編譯器類型。

代碼

#include <iostream> #include <cstdio> #include <map> #include <cmath> using namespace std;int N; map<int,int>cache; int main(int argc, const char * argv[]) {scanf("%d",&N);for (int c = 0; c*c <=N/2 ; ++c) {for (int d = c; c*c+d*d <= N; ++d) {if(cache.find(c*c+d*d)==cache.end())cache[c*c+d*d]=c;}}for (int a = 0; a*a <=N/4 ; ++a) {for (int b = a; a*a+b*b<=N/2 ; ++b) {if(cache.find(N-a*a-b*b)!=cache.end()){int c = cache[N-a*a-b*b];int d=int(sqrt(N-a*a-b*b-c*c));printf("%d %d %d %d\n",a,b,c,d);return 0;}}}return 0; }

簡單代碼

#include <iostream> #include <cmath> using namespace std; bool is_int(int x) {double a=sqrt(x);int b=a;return a-b==0?true:false; } int main() {int n;cin>>n;for(int a=0;a<sqrt(n);a++){for(int b=0;b<sqrt(n);b++){for(int c=0;c<sqrt(n);c++){int x1=a*a+b*b+c*c;if(is_int(n-x1)){int d=n-x1;cout<<a<<' '<<b<<' '<<c<<' '<<sqrt(d)<<endl;goto stop;}}}}stop:return 0; }

總結

以上是生活随笔為你收集整理的征战蓝桥 —— 2016年第七届 —— C/C++A组第8题——四平方和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。