AcWing 1221. 四平方和
原题链接
简单
作者:
muchun
,
2024-04-06 00:03:45
,
所有人可见
,
阅读 1
#include<bits/stdc++.h>
using namespace std;
const int N=5e6;
int a,b,c,d,n;
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;
return d<t.d;
}
};
Sum record[N*2];
int main(){
scanf("%d",&n);
int k=0;
for(int c=0;c*c<=n;++c)
{
for(int d=c;d*d +c*c <= n;++d)
{
record[k++]={d*d +c*c,c,d};
}
}
sort(record, record + k);
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;
int l=0,r=k-1;
while(l<r)
{
int mid=(l+r)/2;
if(record[mid].s>=t)
r=mid;
else
l=mid+1;
}
if(record[l].s==t)
{
{
printf("%d %d %d %d\n", a, b, record[l].c, record[l].d);
return 0;
}
}
}
}
return 0;
}