题目描述
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多 4 个正整数的平方和。
如果把 0 包括进去，就正好可以表示为 4 个数的平方和。
比如：
$5=0^2+0^2+1^2+2^2$
$7=1^1+1^1+1^1+2^2$
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对 4 个数排序：
$0≤a≤b≤c≤d$
并对所有的可能表示法按 $a,b,c,d$ 为联合主键升序排列，最后输出第一个表示法。
输入格式
输入一个正整数 N。
输出格式
输出 4个非负整数，按从小到大排序，中间用空格分开。
数据范围
$0<N<5{\times}10^6$
输入样例：
5输出样例：
0 0 1 2算法分析
$a,b,c,d{\leqslant}N=5{\times}10^6$
$\sqrt(N)=2236.067977$故最多只能枚举两位数($2236^{2236} {\geq}1{\times}10^8$)
故:
- 最多只能枚举2个数
- 空间换时间
第一步：空间换时间方法
for (c = 0; pow(c, 2) <= N; c ++)
for (d = c; pow(c, 2) + pow(d, 2) <= N; d ++)
// 存放c^2 + d^2的值将所有的$c^2+d2$存起来$O(N^2)$
第二步：枚举
for (a = 0; pow(a, 2) <= N; a ++)
for (b = a; pow(b, 2) + pow(c, 2) <= N; b ++)
t = n - pow(c, 2) - pow(d, 2);t表示和最终答案的差是多少$O(N^2)$
此时我们只需要去判断一下这个 t能否用两个数的平方和凑出来即可，
即得到 t后寻找前面$c^2+d2$的值，是否存在与t相等的值。
if (存在与t相等的值)
// 输出answer寻找方法：
- 哈希$O(1)$
- 二分$O(logn)$
第三步：找到字典序最小解
分析：对于 a和 b，是两个 for循环找到的最小的值，因此前两个数可以保证字典序最小。
所以现在我们只需要找到后两个字典序最小的组合即可。
故存放的时候我们不仅要存放$c^2+d^2$的值，还要按照 c,d的字典序排先后顺序。
AC代码
暴力做法：$O(N^3)$ 超时
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2500010;
int n;
int main()
{
cin >> n;
for (int a = 0; a * a <= n; a ++ )
for (int b = a; a * a + b * b <= n; b ++ )
for (int c = b; a * a + b * b + c * c <= n; c ++ )
{
int t = n - a * a - b * b - c * c;
int d = sqrt(t);
if (d * d == t)
{
printf("%d %d %d %d\n", a, b, c, d);
return 0;
}
}
}二分查找：$O(N^2logN)$ 2747 ms
#include <bits/stdc++.h>
using namespace std;
const int N = 5 * 1e6 + 10;
int n, x;
int a, b, c, d;
struct val {
int t, x, y;
};
val V[N];
int m;
bool cmp(val v1, val v2) {
if (v1.t != v2.t) {
return v1.t < v2.t;
} else if (v1.x != v2.x) {
return v1.x < v2.x;
} else {
return v1.t < v2.t;
}
}
int main() {
scanf("%d", &n);
// 存放放c^2和d^2的值
for (c = 0; c * c <= n; c ++) {
for (d = c; c * c + d * d <= n; d ++) {
// 使用数组存放c^2和d^2的值和数据
V[m ++] = {c * c + d * d, c, d};
}
}
// 二分查找需要有序
sort(V, V + m, cmp);
//枚举
for (a = 0; a * a <= n; a ++) {
for (b = a; a * a + b * b <= n; b ++) {
int t = n - a * a - b * b;
// 二分查找
int l = 0, r = m - 1;
while(l < r) {
int mid = l + r >> 1;
if (V[mid].t >= t) r = mid;
else l = mid + 1;
}
if (V[l].t == t) {
printf("%d %d %d %d", a, b, V[l].x, V[l].y);
exit(0);
}
}
}
return 0;
}哈希表$O(N^2)$ 超时
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 2500010;
int n, m;
unordered_map<int, PII> S;
int main()
{
cin >> n;
for (int c = 0; c * c <= n; c ++ )
for (int d = c; c * c + d * d <= n; d ++ )
{
int t = c * c + d * d;
if (S.count(t) == 0) S[t] = {c, d};
}
for (int a = 0; a * a <= n; a ++ )
for (int b = 0; a * a + b * b <= n; b ++ )
{
int t = n - a * a - b * b;
if (S.count(t))
{
printf("%d %d %d %d\n", a, b, S[t].x, S[t].y);
return 0;
}
}
return 0;
}大佬使用air数组直接做的 395 ms
#include<iostream>
#include<map>
using namespace std;
const int MAX=5e6+5;
int n;
pair<int,int> a[MAX];
int main()
{
cin>>n;
for(int i=0;i*i<=n;i++)
{
for(int j=i;i*i+j*j<=n;j++)
{
int t=i*i+j*j;
if(a[t].second==0&&a[t].first==0)
{
a[t]={i,j};
}
}
}
for(int i=0;i*i<=n;i++)
{
for(int j=i;j*j+i*i<=n;j++)
{
int t=n-i*i-j*j;
if(a[t].second!=0||a[t].first!=0)
{
cout<<i<<" "<<j<<" "<<a[t].first<<" "<<a[t].second;
return 0;
}
}
}
return 0;
}