二分求解四平方和(c++实现)

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 2500010;
struct Sum{
    int s,c,d;
}sum[N];
int n,m;

bool cmp(struct Sum s1,struct Sum s2){
    if(s1.s != s2.s) return s1.s < s2.s;
    if(s1.c != s2.c) return s1.c < s2.c;
    return s1.d < s2.d;
}

int main(){
    scanf("%d",&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,cmp);
    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 = 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){
                printf("%d %d %d %d",a,b,sum[r].c,sum[r].d);
                return 0;
            }
        }
    }
    
    
}