题目描述

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

每个正整数都可以表示为至多 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
为联合主键升序排列，最后输出第一个表示法。

样例

输入样例：

5

输出样例：

0 0 1 2

算法1

(暴力枚举 简单优化)

时间复杂度 $ O(n^(3/2)) $

大体思路

输出的a b c d 四个数有大小关系，也就是说axa 的最大值为 n/4
在遍历过程中a 确定下来之后 bxb 的最大值为 (n - axa)/3 最小值为 a
同理 c 的最大值为(n - axa - bxb)/2 最小值为 b
d可以直接算出

Java 代码

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         int n = sc.nextInt();
         for(int i = 0; i*i*4 <n;++i){
            for(int j = i;j*j*3 <n-i*i;++j ) {
                for (int k = j; k*k*2 < n-i*i-j*j ;++k) {
                       int z = (int)Math.sqrt(n-i*i-j*j-k*k);
                        if (i*i+j*j+k*k+z*z == n) {
                            System.out.println(i+" "+j+" "+k+" "+z);
                             return ;
                    }
                }
            }
        }

    }   

}

实际时间复杂度介于 $O(n)$和$O(n^(3/2))$ 之间

4976640 的计算时间为 217ms
4653056 的计算时间为 703ms
比优化前快了一倍多刚好满足时间限制