当前位置:首页 » Project Euler » 详细页

Perfect Square Collection 题号:142 难度: 45 中英对照

Find the smallest x + y + z with integers x > y > z > 0 such that x + y, x − y, x + z, x − z, y + z, y − z are all perfect squares.

Solution

- 如何计算符合要求的x+y+z 假设$$x+y=a^{2},x-y=b^{2},a^{2}>b^{2}$$$$y+z=c^{2},z < y$$那么可以得到$$x=\frac{a^{2}+b^{2}}{2}$$$$y=\frac{a^{2}-b^{2}}{2}$$$$z=c^{2}-y$$接着再判断x+z、x-z、y-z是平方数就可以得到满足要求的值 - 如何求满足要求的最小的x+y+z 设置一个limit,依次找小于该limit的满足条件x+y+z,不断增加limit的值(若干倍的增加),直到找到满足条件的值,此时的limit值记为sumLimit 再找小于sumLimit的满足条件x+y+z,如果没找到就返回该sumlimit,如果找到了,说明有更小的满足条件的x+y+z

Code

public final class p142 {
	static boolean[] isSquare;
	public static void main(String[] args){
		long start=System.nanoTime();
        long result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
	}
	public static long run(){
		long sumLimit = 10;
		// Raise the limit until a sum is found
		while (true) {
			isSquare = new boolean[(int)sumLimit];
			for (int i = 0; i * i < sumLimit; i++)	//将是平方数的数标记为true
				isSquare[i * i] = true;			
			long sum = findSum(sumLimit);
			if (sum != -1) {
				sum = sumLimit;
				break;
			}
			sumLimit*=10;
		}
		
		while (true) {
			long sum = findSum(sumLimit);
			if (sum == -1)  
				return sumLimit;
			sumLimit = sum;
		}
	}
	
	static long findSum(long limit) {
		for (int a = 1; a * a < limit; a++) {
			for (int b = a - 1; b > 0; b--) {
				if ((a + b) % 2 != 0)  // 确保x和y是整数
					continue;
				long x = (a * a + b * b) / 2;
				long y = (a * a - b * b) / 2;
				if (x + y + 1 >= limit)  
					continue;
				
				long zlimit = Math.min(y, limit - x - y);
				for (int c = (int)Math.sqrt(y) + 1; c * c - y < zlimit; c++) {
					long z = c * c - y;
					if (isSquare[(int) (x + z)] && isSquare[(int) (x - z)] && isSquare[(int) (y - z)]){
						//System.out.println(x+" "+y+" "+z+" "+(x+y+z)+" "+limit);
						return x + y + z;
					}
				}
			}
		}
		return -1;
	}
	
}
1006193
476ms