(二分)

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=5000050;
int m,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[N];//在sum中存储c*c+d*d  c d
int main()
{
    cin>>n;
    for(int c=0;c*c<=n;c++)//先把sum中所有状态枚举一遍
    {
        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=a;a*a+b*b<=n;b++)//按照字典序排列a和b
        {
            int t=n-a*a-b*b;
            int l=0,r=m-1;
            while(r>l)
            {
                int mid=r+l>>1;
                if(sum[mid].s>=t) r=mid;
                else l=mid+1;
            }
            if(sum[l].s==t)//sum.s具有单调性 则可使用二分
            {
                cout<<a<<' '<<b<<' '<<sum[l].c<<' '<<sum[l].d<<endl;
                return 0;//按照字典序输出之后返回即可
            }
        }
    }
    return 0;
}