更多精彩文章請關注公眾號『大海的BLOG』
問題：
四平方和定理，又稱為拉格朗日定理：
每個正整數都可以表示為至多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， 不能通過工程設定而省略常用頭檔案，
提交時，注意選擇所期望的編譯器型別，
思路：
這題我是暴力輸出的，用四個回圈，我先前用四個回圈是從小加到大，但是超時了，我發現，輸入的數越大，輸出的前兩個數是比較小的，但是后面兩個數比較大，于是我把后面兩個回圈變成從大減到小，于是accept了
實作代碼(C)
#include<stdio.h>
#include<math.h>
void solve(long n){
int a[4];
for (a[0]=0; a[0]<sqrt(n); a[0]++) {
for (a[1]=a[0];a[1]<sqrt(n) ; a[1]++) {
for (a[2]=sqrt(n-a[1]*a[1]-a[0]*a[0]); a[2]>=a[1]; a[2]--) {
for (a[3]=sqrt(n-a[1]*a[1]-a[2]*a[2]-a[0]*a[0])+1; a[3]>=a[2]; a[3]--) {//其實這里加1不加1都一樣
if (a[0]*a[0]+a[1]*a[1]+a[2]*a[2]+a[3]*a[3]==n) {
printf("%d %d %d %d\n",a[0],a[1],a[2],a[3]);
return ;
}
}
}
}
}
}
int main(){
long n;
scanf("%ld",&n);
solve(n);
return 0;
}
更多精彩文章請關注公眾號『大海的BLOG』
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/36292.html
標籤：C
上一篇：藍橋杯-生日蠟燭
下一篇：藍橋杯-最大子陣