算法1

空间换时间的优化，四重循环变二重

C++ 代码

#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

const int N = 2500;

PII mp[5000010];

int st[5000010];

int mi[N];

int n;

int main()
{
    cin >> n;
    int maxv = sqrt(n);
    for(int i = 1; i <= maxv; ++ i)
        mi[i] = i * i;
    for(int i = 0; i <= maxv; ++ i)
        for(int j = i; j <= maxv; ++ j)
            if(mi[i] + mi[j] <= n && !st[mi[i] + mi[j]])
                {
                    mp[mi[i] + mi[j]] = {i, j};
                    st[mi[i] + mi[j]] = 1;
                }
    int a, b, c, d;
    for(int i = 0; i <= maxv; ++ i)
        for(int j = i; j <= maxv; ++ j)
            if(st[n - mi[i] - mi[j]])
                {
                    PII t = mp[n - mi[i] - mi[j]];
                    a = i, b = j, c = t.x, d = t.y;
                    printf("%d %d %d %d", a, b, c, d);
                    return 0;
                }
    return 0;
}