题目描述
四平方和定理，又称为拉格朗日定理：每个正整数都可以表示为至多 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个非负整数，按从小到大排序，中间用空格分开。
数据范围
1 <= N <= 5 * 10^6
输入样例:
5
输出样例:
0 0 1 2
算法1
(枚举 + 哈希)
刚开始根据题意，直接四重循环暴力枚举a,b,c,d，意料之中的超时了，后来慢慢优化，优化成三重循环，仍然不行(当时没有理解清楚到 a <= b<= c<= d这个关系)，再然后,就想到了打表
- 建立哈希表，存储小于n的数c,假设e = c^2 + d^2,则h[e] = c,从小到大遍历c, d只存储先出现的(因为字典序小)
- 从小到大遍历a、b,查找1中建立的哈希表,若 h[n - a^2 - b^2]存在,则算出d,
时间复杂度 O(n)
空间复杂度 O(n)
C++ 代码
#include<iostream>
#include<cmath>
using namespace std;
const int N = 1e8 + 10;
int h[N];
int main() {
int n;
cin >> n;
//打表，找出1 - n，所有完全平方数两两之和，如果存在只记第一次出现（题目要求找出字典序小的）
for (int i = 0; i * i * 2<= n; i++) {
for (int j = i; j * j + i * i <= n; j++) {
if (!h[i * i + j * j])
h[i * i + j * j] = i + 1;//防止i = 0时在后面判断查找跳过 i = 0的情况
}
}
//0<= a <= b <= c <= d,可以得出a^2 <= n / 4, a^2 + b^ 2 <= n / 2;
for (int i = 0; i * i * 4 <= n; i++) {
for (int j = i; j * j + i * i <= n / 2; j++) {
int t = n - i * i - j * j;
if (h[t]) {
int c = h[t] - 1;
//防止开根号后因为精度关系,向下取整,例:25 开根号得到4.99999向下取整为4;
int d = (sqrt(t - c * c) + 1e-4);
printf("%d %d %d %d", i, j, c, d);
return 0;
}
}
}
return 0;
}
tql
tql
25开根号为什么是4.9999999呢·，我把那个加+ 1e-4删掉也过了
这个题解是暴力吗
tql
tql
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]//用这个头文件
using namespace std;
const int N=2500010;
typedef pair[HTML_REMOVED] PII;
#define x first
#define y second
unordered_map[HTML_REMOVED] S;//用哈希表来存储，有first，second
int n,m;
int main()
{
cin >> n;
for(int c = 0;c <=n;c)
for(int d = c;cc+dd<=n;d)
{
int t=cc+dd;
if(!S.count(t))//如果t没有找到把c，d放进去,此时就是字典序最小的
S[t]={c,d};//就如同数组和关键字
}
for(int a = 0;a <=n;a)
for(int b = a;aa+bb<=n;b)
{
int t=n-(aa+bb);
if(S.count(t))//不为0就说明找到了
printf(“%d %d %d %d”,a,b,S[t].x,S[t].y);
return 0;
}
return 0;
}
/数组模拟哈希表
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
/
输入样例：
5
输出样例：
0 0 1 2
const int N = 5000010;
int hs[N][3];
int n;
int main(int argc, char argv) {
cin >> n;
for(int c = 0; cc <= n; c)
for(int d = c; dd + cc <= n; d){
int tmp = dd + cc;
if(hs[tmp][0] == 0) {
hs[tmp][0] = tmp;
hs[tmp][1] = c;
hs[tmp][2] = d;
}
}
for(int a = 0; aa <= n; a)
for(int b = a; bb + aa <= n; b) {
int left = n - aa-bb;
if(hs[left][0] != 0){
cout << a << ” ” << b << ” ” << hs[left][1] << ” ” << hs[left][2];
return 0;
}
}
return 0;
}
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
const int N=2500010;
int n,m;
struct Sum
{
int s,c,d;
bool operator< (const Sum &t)const
{
if(s!=t.s) return s[HTML_REMOVED]> n;
for(int c = 0;c <=n;c)
for(int d = c;cc+dd<=n;d)
{
sum[m]={
cc+dd,c,d}
;
}
sort(sum,sum+m);
for(int a = 0;a <=n;a)
for(int b = a;aa+bb<=n;b++)
{
int t=n-(aa+bb);
//dd+cc
int l=0,r=m-1;
while(l[HTML_REMOVED]>1;
//在操作数的中间数据
if(sum[mid].s>=t) r=mid;
//假设的dd+cc>t(真正的),说明答案在左边
else l=mid+1;
}
printf(“%d %d %d %d”,a,b,sum[l].c,sum[l].d);
return 0;
}
return 0;
}
为什么这题最后不加 return 0 会输出稀奇古怪的东西
多解，字典序最小输出
请问
h[i * i + j * j] = i + 1;//防止i = 0时在后面判断查找跳过 i = 0的情况我把它改成 = i ，然后在下面判断的时候写成 if(h[t] >= 0) int c = h[t];
为什么不可以呢
不行啊，数组初始化全部都是0，这样会多算很多没有的数据
哦哦好的，谢啦
问一下如何开一个大数组，你的a[1e+8]恰好没超过数组下标的最大值，如何开一个更大的呢
看见你名字我就笑不行了
不吃好的不吃贵的。只吃嘎嘣脆的
老八竟然有女粉。。
//0<= a <= b <= c <= d,可以得出a^2 <= n / 4, a^2 + b^ 2 <= n / 2;
为什么QAQ~QAQ~QAQ~QAQ~QAQ
因为要找的是字典序最小的解，所以答案必然是非降序排列的，a最大的时候就是四个数都相等的时候
（还是不明白）QAQ
大佬太强了
用数组打表的话为什么要开一亿的长度呀？
我开了5e6也没问题
确实啊,知道范围并且只限定数字,直接用数组做map就行,我用自带map比暴力还慢.
#用这个过了！#没用map的find函数
这也不是O(n) 吧
内外层循环都是根号n的，所以打表和后面枚举的两重循环都是O(n)的，由于用的是数组，查表判断是 O(1)的，sqrt函数可能需要点时间，但实际并不高（因为不会枚举到太大的数），所以总体来说近乎是O(n)的
了解，谢谢啦
应该是O(2倍的根号n) 吧
系数的话影响不大，就忽略了
为什么o（n）没过呢 数据不是最多百万级的么