Problem describe

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

比如：
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
（^符號表示乘方的意思）

對于一個給定的正整數(shù)，可能存在多種平方和的表示法。
要求你對4個數(shù)排序：
0 <= a <= b <= c <= d
并對所有的可能表示法按 a,b,c,d 為聯(lián)合主鍵升序排列，最后輸出第一個表示法

程序輸入為一個正整數(shù)N (N<5000000)
要求輸出4個非負(fù)整數(shù)，按從小到大排序，中間用空格分開

例如，輸入：
5
則程序應(yīng)該輸出：
0 0 1 2

再例如，輸入：
12
則程序應(yīng)該輸出：
0 2 2 2

再例如，輸入：
773535
則程序應(yīng)該輸出：
1 1 267 838

---

思考過程

題意：字面意思，注意：聯(lián)合主鍵升序排列 可以理解為 按字典序排列(逐個字母比較)。 如：01234>1。

下等解法：
首先想到的是四重for循環(huán)枚舉，估算了一下時間復(fù)雜度：最極端的情況是：n=500w時，a，b，c，d分別相等(假設(shè)可以相等)，也是就是1118， 那么規(guī)模約為1萬億。 正常一秒約運行1千萬次，因此絕對不可行(當(dāng)然也能得部分步驟分)

中等解法：
接下來考慮：
1、若a，b，c已知，d可以由等式：d=n-a*a-b*b-c*c推出，因此可減為三重循環(huán)， 規(guī)模降為一億；
2、由于題給規(guī)則為：按聯(lián)合主鍵升序排序，因此，滿足等式，a<=b<=c<=d，在枚舉時，加入此限制條件， 問題規(guī)模大致會減少一倍（證明見高斯定理）。 這樣一來，所有的樣例都可以通過了。

上等解法：
當(dāng)然，更優(yōu)化的解法是hash映射。
通過map容器，將c*c+d*d做映射，接下來雙重循環(huán)遍歷a*a和b*b，若n-a*a-b*b存在映射，則說明有合理的a,b,c,d。 輸出即可。

接下來給出兩種代碼。

---

暴力優(yōu)化_代碼

#include<bits/stdc++.h> using namespace std; int main() {ios::sync_with_stdio(false);int n=773535;int len = sqrt(n);for(int i = 0 ; i <= len; i++) for(int j = i; j <= len; j++)for(int k = j; k <= len; k++) {int l = n - i*i - j*j - k*k;if(i*i + j*j + k*k + l*l == n) {int a[4]; a[0]=i; a[1]=j; a[2]=k; a[3]=l;sort(a, a+4);cout << a[0] << ' ' << a[1] << ' ' << a[2] << ' ' << a[3] << endl;return 0;}} return 0; }

---

hash_代碼

#include<bits/stdc++.h> using namespace std; int N; int main() {ios::sync_with_stdio(false);int a, b, c, d;map<int, int>cache;cin>>N;int len = sqrt(N);for(c=0; c*c<=N/2; c++) for(d=0; c*c+d*d<=N; d++) cache[c*c + d*d]=c; //映射平方和for(a=0; a*a<=N/4; a++) for(b=0; a*a+b*b<=N/2; b++) if(cache.find(N-a*a-b*b) != cache.end()) { //找不到則返回cache.end（）c = cache[N-a*a-b*b];d = (int)(sqrt(N-a*a-b*b-c*c));cout << a << ' ' << b << ' ' << c << ' ' << d <<'\n'; return 0;} return 0; }

---

---

登天難，求人更難。黃連苦，無錢更苦。江湖險，人心更險。春冰薄，人情更薄。既落江湖內(nèi)，便是薄命人。但行好事，莫問前程。

總結(jié)

以上是生活随笔為你收集整理的暴力优化解法+哈希解法——2016年第七届蓝桥杯省赛b组第八题 四平方和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。