四平方和——AcWing 1221

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 5000010;

struct solve {
    int a,b,su;
}s[N];

bool cmp(solve x,solve y){
    if (x.su != y.su) return x.su < y.su;
    if (x.a != y.a) return x.a < y.a;
    return x.b < y.b;
}

int main(){
    int n;
    scanf("%d",&n);
    int m = 0;
    for (int i  = 0; i * i <= n; i ++){
        for (int j = i; i * i + j *j <= n; j++){ //     c ，d     
            s[m].a = i;
            s[m].b = j;
            s[m].su = i * i + j * j;
            m ++;
        }
    }
    sort(s,s + m, cmp);  //      ，    
    for (int i = 0; i * i <= n; i++){
        for (int j = i; j * j + i *i <= n; j++){
            int t = n - i * i - j * j;  //        
            int l = 0; 
            int r = m - 1;
            while(l < r){  //   
                int mid = l + r >> 1;
                if (s[mid].su >= t) r = mid;
                else l = mid + 1;
            }
            if (s[l].su == t) {
                printf("%d %d %d %d
",i,j,s[l].a,s[l].b);
                return 0;
            }
        }
    }
    return 0;
}