$$\color{Red}{四平方和【二分法和哈希表法】}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

四平方和定理，又称为拉格朗日定理：

每个正整数都可以表示为至多 4 个正整数的平方和。

如果把 0 包括进去，就正好可以表示为 4 个数的平方和。

对于一个给定的正整数，可能存在多种平方和的表示法。

要求你对 4 个数排序：

0 ≤ a ≤ b ≤ c ≤ d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法。

输入格式

输入一个正整数 N。

输出格式

输出4个非负整数，按从小到大排序，中间用空格分开。

数据范围

0 < N < 5 ∗ 10 ^ 6

输入样例：

5

输出样例：

0 0 1 2

题目思路

三重循环枚举会超时，这里y总提供的思路是，我们先找寻两个数的平方和满足小于等于n，先枚举的这两个数是 c , d。

如何保证 c 和 d满足字典序排列？

循环的过程中，让 d从 等于c开始枚举即可，然后放入一个Arraylist集合。

为了让我们满足搜索答案具有单调性，且满足题目要求的字典序。我们让这个集合从大到小排序，应该满足先按他们的平方和进行排序，在此基础上再按 c 和 d的字典序。

然后接着两层循环找寻 a 和 b，和上面思路相同，这里其实不需要非得给循环加入条件，因为我们嵌套循环天生满足先搜到的答案，必然’b >= a’，但是加上能剪枝。

搜到满足四个数平方和等于答案的第一个解，就是满足题目要求的字典序递增的解。

二分法

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main {
    static int n;
    static List<int[]> list = new ArrayList<>();
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        for (int c = 0; c * c <= n; c++) {
            for (int d = c; d * d + c * c <= n; d++) {
                list.add(new int[]{c * c + d * d, c, d});
            }
        }
        Collections.sort(list, (o1, 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 a = 0; a * a <= n; a++) {
            for (int b = a; a * a + b * b <= n; b++) {
                int t = n - a * a - b * b;
                int l = 0, r = list.size() - 1;
                while (l < r) {
                    int mid = l + r >> 1;
                    if (list.get(mid)[0] < t) l = mid + 1;
                    else r = mid;
                }
                if (list.get(l)[0] == t){
                    int c = list.get(l)[1];
                    int d = list.get(l)[2];
                    System.out.println(a + " " + b + " " + c + " " + d);
                    return;
                }
            }
        }
    }
}

哈希表法

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    static int n;
    static Map<Integer, int[]> map = new HashMap<>();
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        for (int c = 0; c * c <= n; c++)
            for (int d = c; d * d + c * c <= n; d++) {
                int x = d * d + c * c;
                if (!map.containsKey(x)) {
                    map.put(x, new int[]{c, d});
                }
            }

        for (int a = 0; a * a <= n; a++) {
            for (int b = a; b * b + a * a <= n; b++) {
                int t = n - b * b - a * a;
                if (map.containsKey(t)){
                    int[] array = map.get(t);
                    System.out.printf("%d %d %d %d",a, b, array[0], array[1]);
                    return;
                }
            }

        }
    }
}