·【蓝桥】·四平方和

一道不错的哈希/二分题目~
题目链接：·【蓝桥】·四平方和

感谢优秀博客1：二分/哈希-蓝桥杯省赛-四平方和
感谢优秀博客2：蓝桥杯 四平方和

题目描述
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多 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。
输出格式
输出4个非负整数，按从小到大排序，中间用空格分开。
数据范围
0<N<5∗10^6
输入样例：
5
输出样例：
0 0 1 2

题目分析

  1. 要求将一个数分解为4个数平方和的形式，要求4个数升序并且尽可能小。
    分析得a b c d的枚举范围：[0,sqrt(5000000)]
  2. 最初的思路是：枚举a,b,c 判断N-a^2-b^2-c^2是否为平方数，算法复杂度O(N^1.5),妥妥超时
    从N的规模可推测出程序的效率应该最多O(N)或O(N log N)
  3. 所以只枚举a,b 可得到N-a^2-b^2，接下来就是求c^2+d^2 = N-a^2-b^2
    最后确定c,d的值，哈希的时间复杂度O(N), 二分的时间复杂度就要O(N log N)

哈希优化枚举（181ms AC）

算法思想
哈希表f[]记录c^2+d^2的结果，可令 f[c*c+d*d] = c;
这个数组f要开到5*10^6，用空间换时间的思想可使查询c,d在O(1)的效率下完成

———————————————完整代码————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//哈希
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

int num[5000005];
int n;
int main(){
	scanf("%d", &n);
	for(int i = 0; i*i <= n; ++i){
		for(int j = i; i*i+j*j <= n; ++j){
			if(num[i*i+j*j] == 0)
				num[i*i+j*j] = j;
		}
	}
	for(int a = 0; a*a <= n; ++a){
		for(int b = a; a*a+b*b <= n; ++b){
			if(num[n-a*a-b*b] != 0){
				int d = num[n-a*a-b*b];
				int c = int(sqrt(n-a*a-b*b-d*d)+1e-3);//sqrt返回值为浮点数，有精度误差
				cout <<a<<" "<<b<<" "<<c<<" "<<d<<endl;		
				return 0;
			}
		}
	}
	return 0;
}

二分优化枚举（2740ms AC）

算法思想
如果能通过哈希的方法解决该题，二分就很容易理解了
将所有的c^2+d^2结果存储起来（相加结果相同的不去重），二分求c和d
——————————————完整代码————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//二分
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int N = 2500010;
struct node
{
    int t,c,d;
    bool operator<(const node&tmp)
    {
        if(t!=tmp.t) return t<tmp.t;
        if(c!=tmp.c) return c<tmp.c;
        return d<tmp.d;
    }
}num[N];
int n,cnt;

int main()
{
    cin>>n;
    for(int c=0;c*c<=n;c++)
        for(int d=c;c*c+d*d<=n;d++)
        {
            num[cnt++]={c*c+d*d,c,d};
        }
    sort(num,num+cnt);//同一值可能对应多组c和d，所以先排序

    for(int a=0;a*a<=n;a++)
        for(int b=a;a*a+b*b<=n;b++)//二分来求c和d
        {
            int tmp=n-a*a-b*b;//二分求c^2+d^2=tmp的下标
            int l = 0, r = cnt-1;
			while(l < r){
				int mid = (l+r)>>1;
				if(num[mid].t < tmp)
					l = mid+1;
				else if(num[mid].t > tmp)
					r = mid-1;
				else{
					r = mid;
				}  
			}
			if(num[l].t == tmp){
			    cout << a<<" "<<b<<" "<<num[l].c<<" "<<num[l].d<<endl;
				return 0;
			}
        }

    return 0;
}