再探四方定理

1464058514

题目描述
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多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 (N<5000000)
要求输出4个非负整数，按从小到大排序，中间用空格分开
例如，输入：

5

则程序应该输出：

0 0 1 2

再例如，输入：

12

则程序应该输出：

0 2 2 2

再例如，输入：

773535

则程序应该输出：

1 1 267 838

资源约定：
峰值内存消耗（含虚拟机） < 256M

CPU消耗 < 3000ms

这是今年省赛的题目，不得不说，当时我竟用dfs搞不出

题目原文链接

解法一(这是当时赛后想出来比较完美的解法)

public class A9 {

static int[] mpt = new int[5000010];
static int n;

static void init() {
    for (int i = 0; i * i <= n; i++)
        for (int j = 0; j * j <= n; j++)
            if (i * i + j * j <= n)
                mpt[i * i + j * j] = 1;
}

public static void main(String[] args) {
    boolean flag = false;
    Scanner scanner = new Scanner(System.in);
    n = scanner.nextInt();
    init();
    for (int i = 0; i * i <= n; i++) {
        for (int j = 0; j * j <= n; j++) {
            if (mpt[n - i * i - j * j] == 0)
                continue;// 如果剩下的差用两个完全平方数不能组合出来就不继续
            for (int k = 0; k * k <= n; k++) {
                int temp = n - i * i - j * j - k * k;
                double w = Math.sqrt(temp);
                if (w == (int) w) {
                    System.out.printf("%d %d %d %d ", i, j, k, (int) w);
                    flag = true;
                    break;
                }
            }
            if (flag)
                break;
        }
        if (flag)
            break;
    }
    scanner.close();
}

}

解法二（DFS）

import java.util.Scanner;

public class SiFangshu {

// 从最大数开始验证
static boolean f(int number, int[] a, int n) {
    if (number == 0)
        return true;
    if (n == 4)
        return false;
    for (int i = (int) Math.sqrt(number); i >= 1; i--) {
        a[n] = i;
        if (f(number - i * i, a, n + 1))
            return true;
    }
    return false;
}

// 从0开始验证
static boolean w(int number, int[] a, int n) {
    if (number == 0)
        return true;
    if (n == 4)
        return false;
    for (int i = 0; i <= (int) Math.sqrt(number); i++) {
        a[n] = i;
        if (w(number - i * i, a, n + 1))
            return true;
    }
    return false;
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int[] a = new int[] { 0, 0, 0, 0 };
    w(n, a, 0);
    System.out.println(a[0] + "-" + a[1] + "-" + a[2] + "-" + a[3]);
    scanner.close();
}

}

实现起来用DFS简单，但是有时缺还不如解法一速度快，因为有些数是没有0的

如果是从高位开始那就是DFS快。

不过从低位开始遍历也是可以优化的