分析

• 数据范围5e6，实际abcd的范围应该开个根号，大概2.4e3，找确定abc，d就确定了，直接判断就行。
• 如何确定abc
  • 1.暴力abc全部枚举一遍，理论上有可能过，因为a<=b<=c，但是过不了。O(N^3)
  • 2.空间换时间，改进暴力算法，目的是改进暴力算法第三次循环找c和d的速度，等价于判断一个数能否表示为c和d的平方和,O(N^2)
    • 1.把存c^2+d^2枚举并存起来，O(N^2)；
    • 2.枚举a^2+b^2的时候，看看n-a^2-b^2是否在表中，O(N^2)；
    • 问题：为什么是字典序，即为什么a<=b<=c<=d？
    • 显然，a<=b，c<=d。哈希表中，按照平方和顺序存储，而在枚举a^2+b^2的时候，也是顺序。当（a^2+b^2+c^2+d^2=n）成立，abcd的任选2个，都是平方和，都已经被顺序存在哈希表中。即：若b>c，a^2+c^2在表中，a^2+b^2也在表中。先枚举到的，肯定是较小的，所以b<=c。

code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
/*
输入样例：
5
输出样例：
0 0 1 2
*/
const int N = 5000010;
int hs[N][3];
int n;

int main(int argc, char** argv) {
    cin >> n;
    for(int c = 0; c*c <= n; c++)
        for(int d = c; d*d + c*c <= n; d++){
            int tmp = d*d + c*c;
            if(hs[tmp][0] == 0) {
                hs[tmp][0] = tmp;
                hs[tmp][1] = c;
                hs[tmp][2] = d;
            }
        }
    for(int a = 0; a*a <= n; a++)
        for(int b = a; b*b + a*a <= n; b++) {
            int left = n - a*a-b*b;
            if(hs[left][0] != 0){
                cout << a << " " << b << " " << hs[left][1] << " " << hs[left][2];
                return 0;
            }
        }
    return 0;
}