2016年省赛 四平方和 java 暴力

暴力

我们要找到每个数的上限值，就是对给出的n进行开根号，求得每个数的上限为2236.0679…，故我们枚举到2237即可；不用四层循环，可以通过将d的平方dd表示出来，判断其开方是否为整数即可；

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 求得a,b,c,d每个数的上限，不然直接枚举到5000000会超时
		// System.out.println(Math.sqrt(5000000));//2236.0679
		int n = sc.nextInt();
		// 枚举a,b,c,d
		for (int a = 0; a <= 2237; a++) {
			for (int b = 0; b <= 2237; b++) {
				for (int c = 0; c <= 2237; c++) {
					// 减少一层循环，节省时间
					int dd = n - a * a - b * b - c * c;// d的平方
					int d = (int) Math.sqrt(dd);// dd开根号得到的值
					// 如果dd开方为整数，那么就是找的答案
					if (dd == d * d) {
						System.out.println(a + " " + b + " " + c + " " + d);
						return;
					}
						
				}
			}
		}
	}
}