用空间换时间
方法一 暴力(会超时)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=5000010;
int main(){
int n;
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 temp=n-a*a-b*b-c*c;
int d=sqrt(temp);
if(d*d==temp) {//看一下d是不是整数
cout<<a<<' '<<b<<' '<<c<<' '<<d<<endl;
return 0;
}
}
return 0;
}
方法二 二分
最多只能枚举两个数 用空间换时间 把cc+dd的值枚举出来之后,用结构体数组存下来,再用sort函数从小到大排序(记得在结构体中重载小于号),再枚举ab,然后二分查找出符合条件的最小cd
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=5000010;
int n,m;
struct Sum{
int s,c,d;
bool operator < (const Sum & t ) const{
if(s!=t.s) return s<t.s;
if(c!=t.c) return c<t.c;//重载小于号 用于在sort中排序 先按s排序,如果s一样按c排,c一样按d排
return d<t.d;
}
}sum[N];
int main(){
cin>>n;
//枚举c,d 存在sum[m]中
for(int c=0;c*c<=n;c++)
for(int d=c;c*c+d*d<=n;d++){
sum[m]={c*c+d*d,c,d};
m++;
}
//用sort从小到大排序(字典序)
sort(sum,sum+m);
//枚举a,b
for(int a=0;a*a<=n;a++)
for(int b=a;a*a+b*b<=n;b++){
int t=n-a*a-b*b;
//二分查找符合条件的c,d
int l=0,r=m-1;
while(l<r){
int m=l+r>>1;
if(sum[m].s>=t) r=m;
else l=m+1;
}
//判断为整数 输出
if(sum[l].s==t) {
cout<<a<<' '<<b<<' '<<sum[l].c<<' '<<sum[l].d<<endl;
return 0;
}
}
return 0;
}
方法三 用哈希表(优势:只存第一个值—最小值)
(哈希表还不太会用)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=5000010;
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};//如果S.count(t)==0 即t之前没有存过 把c,d存下来
}
for(int a=0;a*a<=n;a++)
for(int b=a;a*a+b*b<=n;b++){
int t=n-a*a-b*b;
if(S.count(t)) {
cout<<a<<' '<<b<<' '<<S[t].x<<' '<<S[t].y<<endl;
return 0;
}
}
return 0;
}
二分的循环条件为什么不是≤呀