你好呀，我是灰小猿，一個超會寫bug的程式猿！

歡迎大家關注我的專欄「每日藍橋」，該專欄的主要作用是和大家分享近幾年藍橋杯省賽及決賽等真題，解析其中存在的演演算法思想、資料結構等內容，幫助大家學習到更多的知識和技術！

標題：四平方和

四平方和定理，又被稱為拉格朗日定理。

每個正整數都可以表示為至多四個正整數的平方和，

如果把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<500000）

要求輸出4個非負整數，按從小到大排序，中間用空格分開，

例如：輸入
5

則程式應該輸出：

0 0 1 2

 

再例如，輸入：

12

則程式輸出：

0 2 2 2

 

再例如，輸入：

773535

程式輸出：

1 1 267 838

 

【資源約定】

峰值記憶體消耗（含虛擬機器器）< 256M

CPU消耗 < 3000ms

請嚴格按要求輸出，不要畫蛇添足的列印類似「請您輸入...」的多餘內容。

所有程式碼放在同一個原始檔中，偵錯通過後，拷貝提交該原始碼。

注意：不要使用package語句，不要使用jdk1.6及以上的版本特性

注意：主類的名稱必須是Main 否則按無效程式碼處理。

解題思路：

本題在求解上主要使用的還是暴力列舉的方法，但是對於這道題來講，四個for迴圈的巢狀在迴圈上是十分佔用記憶體和CPU的，所以即使使用了迴圈巢狀語句，也應該對其進行合理的優化減少迴圈次數，所以應該清楚每一個數的取值範圍，之後簡化迴圈，

第二種方法是儘可能的減少迴圈的次數，所以我們可以僅僅只對前兩個數進行迴圈，之後判斷N與前兩個數的平方和的差值，是否是兩個數的平方和，如果是，則說明符合題目要求，因此我們需要先將兩個數的平方和在map中進行儲存，之後才能進行判斷，當判斷成功之後，這個時候輸出四個數並且跳出迴圈即可，

下面是這兩種解法的程式碼：

答案原始碼：

解法一：

public class Year2016_Bt8 {

	static int N; 
	static int [] ansArr = new int[4];
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		N = scanner.nextInt();
		//對答案陣列進行初始化
		for (int i = 0; i < 4; i++) {
			ansArr[i] = N;
		}
		
		int [] Arr = new int[4];//定義存放臨時答案的陣列
		/**
		 * 根據題目要求確定每一個數位的範圍
		 * 設數位從第一個a開始，之後的數逐漸增大，所以第一個數最大應該是N除以4份之後，開平方
		 * */
		for (int a = 0; a <= (int)Math.sqrt(N/4)+1; a++) {
			if (a*a>N||a>ansArr[0]) break;//如果該數的平方或該數已經大於正確答案的第一個數，則不再進行之後的迴圈
			for (int b = a; b <= (int)Math.sqrt(N/3)+1; b++) {
				if(a*a+b*b>N) break;
				for (int c = b; c <= (int)Math.sqrt(N/2)+1; c++) {
					if(a*a+b*b+c*c>N) break;
					for (int d = c; d <= (int)Math.sqrt(N)+1; d++) {
						if (a*a+b*b+c*c+d*d>N) break;
						if (a*a+b*b+c*c+d*d==N) {
							Arr[0] = a;
							Arr[1] = b;
							Arr[2] = c;
							Arr[3] = d;
							check(Arr);
							break;
						}
					}
				}
			}
		}
		
		System.out.println(ansArr[0] + " " + ansArr[1] + " " + ansArr[2] + " " + ansArr[3]);
	}
	
	//將新得到的答案和上一個答案對比，並將較小的陣列存放到答案陣列中
	private static void check(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			if (arr[i]<ansArr[i]) {
				ansArr[0] = arr[0];
				ansArr[1] = arr[1];
				ansArr[2] = arr[2];
				ansArr[3] = arr[3];
				return;
			}
			if (arr[i]>ansArr[i]) {
				return;
			}
		}
		
	}

}

解法二：

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Year2016_Bt8_2 {

	static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		for (int c = 0; c*c <= N/2 ; c++) {
			for (int d = 0; c*c+d*d<=N; d++) {
				//如果查詢到的是空，說明map中未儲存該數值
				if (map.get(c*c+d*d)==null) {
					map.put(c*c+d*d, c);//將鍵值進行儲存
				}
			}
		}
		
		//迴圈遍歷列舉可能的數值
		for (int a = 0; a <= N/4; a++) {
			for (int b = 0; a*a+b*b <= N/2; b++) {
				//這裡判斷N與前兩個數的平方和的差值，是否是兩個數的平方和
				//根據上面儲存到map中的鍵值對，如果不等於null，則說明存在
				if (map.get(N-a*a-b*b)!=null) {
					int c = map.get(N-a*a-b*b);//獲取到c
					int d = (int)Math.sqrt(N-a*a-b*b-c*c);//獲取到d
					System.out.println(a + " " + b + " " + c + " " + d);
					return;//跳出迴圈結束
				}
			}
		}

	}

}

輸出樣例：

 

其中有不足或者改進的地方，還希望小夥伴留言提出，一起學習！

感興趣的小夥伴可以關注專欄！

灰小猿陪你一起進步！