暴力优化解法+哈希解法——2016年第七届蓝桥杯省赛b组第八题 四平方和

Problem describe

四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多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

---

思考过程

题意：字面意思，注意：联合主键升序排列 可以理解为 按字典序排列(逐个字母比较)。 如：01234>1。

下等解法：
首先想到的是四重for循环枚举，估算了一下时间复杂度：最极端的情况是：n=500w时，a，b，c，d分别相等(假设可以相等)，也是就是1118， 那么规模约为1万亿。 正常一秒约运行1千万次，因此绝对不可行(当然也能得部分步骤分)

中等解法：
接下来考虑：
1、若a，b，c已知，d可以由等式：d=n-a*a-b*b-c*c推出，因此可减为三重循环， 规模降为一亿；
2、由于题给规则为：按联合主键升序排序，因此，满足等式，a<=b<=c<=d，在枚举时，加入此限制条件， 问题规模大致会减少一倍（证明见高斯定理）。 这样一来，所有的样例都可以通过了。

上等解法：
当然，更优化的解法是hash映射。
通过map容器，将c*c+d*d做映射，接下来双重循环遍历a*a和b*b，若n-a*a-b*b存在映射，则说明有合理的a,b,c,d。 输出即可。

接下来给出两种代码。

---

暴力优化_代码

#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; }

---

---

登天难，求人更难。黄连苦，无钱更苦。江湖险，人心更险。春冰薄，人情更薄。既落江湖内，便是薄命人。但行好事，莫问前程。

总结

以上是生活随笔为你收集整理的暴力优化解法+哈希解法——2016年第七届蓝桥杯省赛b组第八题 四平方和的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。