AcWing 1221. 四平方和
原题链接
简单
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 5e6 + 5;
int n,m;
struct node{
int s, c, d;
bool operator < (const node& x)const{
if(s != x.s) return s < x.s;
if(c != x.c) return c < x.c;
else return d < x.d;
}
}sum[N];
int main(){
cin >> n;
for(int c = 0; c * c <= n; c++){
for(int d = 0; d * d <= n - c * c; 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; b * b <= n - a * a; b++){
int t = n - a * a - b * b;
//int pos = lower_bound(sum, sum + m, t) - sum;
int l = 0, r = m - 1;
while(l < r){
int mid = l + r >> 1;
if(sum[mid].s < t){
l = mid + 1;
}else{
r = mid;
}
}
if(sum[l].s == t){
cout << a << " " << b << " " << sum[l].c << " " << sum[l].d << endl;
return 0;
}
}
}
return 0;
}