题目描述

二分或者手写哈希

二分

import java.util.*;

public class Main {
    static final int N = 5000010;

    static class sum{
        int x;
        int y;
        int z;

        sum(int x ,int y , int z){
            this.x = x;
            this.y = y;
            this.z = z;
        }

    }

    static ArrayList<sum> g = new ArrayList<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        //枚举所有c和d的组合
        for (int c = 0; c * c <= n; c++) {
            for (int d = c; d * d + c * c <= n; d++) {
                int s = c * c + d * d;
                 g.add(new sum(c,d,s));
            }
        }

        //按z值排序
        g.sort((p1,p2)->p1.z-p2.z);

        //枚举所有a和b的组合
        for (int a = 0; a * a <= n; a++) {
            for (int b = a; a * a + b * b <= n; b++) {
                int s = n - a * a - b * b;
                //二分
                int l = 0; int r = g.size() - 1;
                while(l < r){
                    int mid = l + r >> 1;
                    //如果z >= s 要找到那个最小能满足的
                    if(g.get(mid).z >= s) r = mid;
                    else l = mid + 1;
                }
                if(g.get(r).z == s){
                    System.out.println(a + " " + b + " " + g.get(r).x + " " + g.get(r).y);
                    return;
                }
            }
        }
    }
}

手写哈希

import java.util.*;

public class Main {
    static final int N = 5000010;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int[] C = new int[N];
        int[] D = new int[N];

        Arrays.fill(C,-1);
        Arrays.fill(D,-1);

        //枚举所有c和d的组合
        for (int c = 0; c * c <= n; c++) {
            for (int d = c; d * d + c * c <= n; d++) {
                int s = c * c + d * d;
                //如果这个和(坑)没被用过,才填进去
                if (C[s] == -1) {
                    C[s] = c;
                    D[s] = d;
                }
            }
        }

        //枚举所有a和b的组合
        for (int a = 0; a * a <= n; a++) {
            for (int b = a; a * a + b * b <= n; b++) {
                int s = n - a * a - b * b;
                //如果s出现过，就输出
                if (s >= 0 && C[s] != -1) {
                    System.out.println(a + " " + b + " " + C[s] + " " + D[s]);
                    return;
                }
            }
        }
    }
}