做法一：hash法

预处理c和d的平方和，存字典值小的，找a和b时进行查表即可

做法二：二分法

import java.util.*;

public class Main {
    static ArrayList<int[]> list = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        for (int i = 0; i * i <= n; i++)
            for (int j = i; i * i + j * j <= n; j++)
                list.add(new int[]{i * i + j * j, i, j});

        //升序排序：优先级：0(s) > 1(c) > 2(d)
        list.sort((int[] o1, int[] o2) -> {
                if (o1[0] != o2[0]) return o1[0] - o2[0];
                if (o1[1] != o2[1]) return o1[1] - o2[1];
                return o1[2] - o2[2];
            });

        for (int i = 0; i * i <= n; i++)
            for (int j = i; i * i + j * j <= n; j++) {
                int t = n - i * i - j * j;
                int l = 0, r = list.size() - 1;
                /*
                 二分：寻找左边界(r = mid),寻找右边界(l = mid)
                 需要r = mid，如果是l = mid的话会出现下面问题
                 我们要找的是4，此时l = 0， r = 4,
                 序列为：1444，l = mid就会找到第二个4从而跳过答案
                */
                while (l < r) {
                    int mid = l + r >> 1;
                    if (list.get(mid)[0] >= t) r = mid;
                    else l = mid + 1;
                }

                if (list.get(l)[0] == t) {//不需要进行排序了
                    int c = list.get(l)[1];
                    int d = list.get(l)[2];
                    System.out.printf("%d %d %d %d", i, j, c, d);
                    return;
                }
            }
    }
}