二分

#include <iostream>
#include <algorithm>
using namespace std;
struct node{
    int c, d;
    int sum;
};
const int N = 5000010;
node p[N];
bool cmp(node a, node b){
    if(a.sum != b.sum)  return a.sum < b.sum;
    return a.c < b.c;
}
int main(){
    int n;  cin >> n;
    int k = 0;
    for(int c = 0; c * c <= n; c ++ ){
        for(int d = c; d * d + c * c <= n; d ++ ){
            p[k ++ ] = {c, d, c * c + d * d};
        }
    }
    sort(p, p + k, cmp);
    for(int a = 0; a * a <= n; a ++ ){
        for(int b = a; b * b + a * a <= n; b ++ ){
            int find = n - a * a - b * b;
            int l = 0, r = k - 1;
            while(l < r){
                int mid = l + r >> 1;
                if(p[mid].sum >= find)  r = mid;
                else    l = mid + 1;
            }
            if(p[l].sum == find){
                cout << a << " " << b << " " << p[l].c << " " << p[l].d << endl;
                return 0;
            }
        }
    }
    return 0;
}

空间换时间

#include <iostream>
using namespace std;
struct node{
    int c, d;
    int flag;
};
node mp[5000010];
int main(){
    int n;
    cin >> n;
    // int k = 0;
    for(int c = 0; c*c <= n; c ++ ){
        for(int d = c; d*d+c*c <= n; d ++ ){
            int sum = c*c+d*d;
            if(!mp[sum].flag){
                mp[sum] = {c, d, 1};
            }
        }
    }
    for(int a = 0; a*a <= n; a ++ ){
        for(int b = a; b*b+a*a <= n; b ++ ){
            int other = n - a*a - b*b;
            if(mp[other].flag){
                cout << a << " " << b << " " << mp[other].c << " " << mp[other].d << endl;
                return 0;
            }
        }
    }
    return 0;
}