题目

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

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

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

比如：

\(5=0^2+0^2+1^2+2^2\) \(7=1^2+1^2+1^2+2^2\)

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

要求你对 4 个数排序：

0≤a≤b≤c≤d

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

输入格式

输入一个正整数 N 。

输出格式

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

数据范围

\(0<N<5∗10^6\)

输入样例：

输出样例：

0 0 1 2

分析

利用空间换时间，首先将\(c^2 + d^2\)的所有结果保存，然后枚举\(a^2 + b^2\)的结果，用二分在之前保存的结果中查找

保存\(c^2 + d^2\)的结果时，由于题目中有对键值排序的要求，所以利用要按\(c^2 + d^2, c, d\)优先级排序

java中接口在排序中的使用

首先定义实现比较接口的类，在这个类中定义构造函数和重写比较函数

class Square_sum implements Comparable<Square_sum> {
    int sum_square, c, d;
    public Sum_square(int sum_square, int c, int d) {
        this.sum_square = sum_square;
        this.c = c;
        this.d = d;
    }
    @Override
    public int compareTo(Square_sum t) {
        if(this.sum_square != t.sum_square) return Integer.compare(this.sum_square, t.sum_square);
        if(this.c != t.c) return Integer.compare(this.c, t.c);
        return Integer.compare(this.d, t.d);
    }
}

然后定义类数组

1	static Square_sum[] data = new Square_sum[MAXSIZE];

接着实例化类数组中每一个对象

1	data[k++] = new Square_sum(c * c + d * d, c, d)

利用Arrays.sort排序，Arrays.sort会使用类数组中重写的比较函数作为排序依据

java加速读取与打印的方法

利用BufferdReader和BuffedWriter

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(reader.readLine())
writer.write(String.format("%d %d %d %d\n"), a, b, c, d)

代码

import java.io.*;
import java.util.Arrays;
class Sum_square implements Comparable<Sum_square> {
    int square_sum, c, d;

    public Sum_square(int square_sum, int c, int d) {
        this.square_sum = square_sum;
        this.c = c;
        this.d = d;
    }

    @Override
    public int compareTo(Sum_square t) {
        if (this.square_sum != t.square_sum) return Integer.compare(this.square_sum, t.square_sum);
        if (this.c != t.c) return Integer.compare(this.c, t.c);
        return Integer.compare(this.d, t.d);
    }
}

public class Main {
    static int MAXNUM = (int) 5e6;
    static Sum_square[] record_sum_square = new Sum_square[MAXNUM];

    public static void main(String[] args) {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))) {

            int n = Integer.parseInt(reader.readLine());
            int count = 0;

            for (int c = 0; c * c <= n; c++) {
                for (int d = c; c * c + d * d <= n; d++) {
                    record_sum_square[count++] = new Sum_square(c * c + d * d, c, d);
                }
            }

            Arrays.sort(record_sum_square, 0, count);
            boolean flag = false;

            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 start = 0, end = count - 1;
                    int mid;

                    while (start < end) {
                        mid = (start + end) / 2;
                        if (record_sum_square[mid].square_sum >= t) {
                            end = mid;
                        } else {
                            start = mid + 1;
                        }
                    }

                    if (record_sum_square[start].square_sum == t) {
                        writer.write(String.format("%d %d %d %d\n", a, b, record_sum_square[start].c, record_sum_square[start].d));
                        flag = true;
                        break;
                    }
                }

                if (flag) {
                    break;
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

Pilot's Blog

Acwing1221拉格朗日定理

题目