四平方和(哈希 / 二分 两种方法)
经典空间换时间,先枚举后两个数c, d并且储存下来,再枚举前两个数a, b,然后通过n - a^2 - b^2 = c^2 + d^2的形式找答案(二分只是在找的时候利用二段性找答案)
哈希表法
#include<iostream>
using namespace std;
const int N = 5000010;
bool st[N];
int c[N], d[N];
int main(){
int n;
cin >> n;
//规定 a b c d 严格非递减 枚举 c d再枚举 a b
for(int i = 0; i * i <= n; i ++){
for(int j = i; j * j + i * i <= n; j ++){
int t = i * i + j * j;
if(!st[t]){ //从小到大枚举 因此第一次枚举到这个数的组合是最小的
st[t] = true;
c[t] = i, d[t] = j;
}
}
}
//枚举完c和d后 枚举a和b(枚举答案) n - a^2- b^2看看答案是否在bool中 则表明是否枚举到了c和d
for(int a = 0; a * a <= n; a ++){
for(int b = a; a * a + b * b <= n; b ++){
int r = n - a * a - b * b;
if(st[r]){
cout << a << ' ' << b << ' ' << c[r] << ' ' << d[r] << endl;
return 0;
}
}
}
return 0;
}
二分
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2500010;
struct Sum{
int s,c,d;
bool operator < (const Sum &A)const{
if(s != A.s) return s < A.s;
if(c != A.c) return c < A.c;
return d < A.d;
}
}sum[N];
int n,m;
int main(){
cin>>n;
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};
}
}
sort(sum,sum+m);
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;
int l = 0, r = m - 1;
while(l < r){
int mid = l + r >> 1;
if(sum[mid].s >= t) r = mid;
else l = mid + 1;
}
if(sum[r].s == t) {
cout<< a <<" "<< b << " " << sum[r].c <<" "<< sum[r].d <<endl;
return 0;
}
}
}
好牛啊博主