### 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