### Pythagorean tiles题号：139 难度： 50 中英对照

Let (a, b, c) represent the three sides of a right angle triangle with integral length sides. It is possible to place four such triangles together to form a square with length c.

For example, (3, 4, 5) triangles can be placed together to form a 5 by 5 square with a 1 by 1 hole in the middle and it can be seen that the 5 by 5 square can be tiled with twenty-five 1 by 1 squares.

However, if (5, 12, 13) triangles were used then the hole would measure 7 by 7 and these could not be used to tile the 13 by 13 square.

Given that the perimeter of the right triangle is less than one-hundred million, how many Pythagorean triangles would allow such a tiling to take place?

### Code

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public final class p139 {
private static final int LIMIT = 100000000;
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 count = 0;
for (int s = 3; s * s / 2 < LIMIT; s += 2) {
for (int t = 1; t < s; t += 2) {
int a = s * t;
int b = (s * s - t * t) / 2;
int c = (s * s + t * t) / 2;
int p = a + b + c;
if (p >= LIMIT)
break;
if (c % (a - b) == 0 && gcd(s, t) == 1){
count += (LIMIT - 1) / p;
//System.out.println(a+" "+b+" "+c+" "+p);
}
}
}
return count;
}
public static int gcd(int x, int y) {
if (x < 0 || y < 0)
throw new IllegalArgumentException("Negative number");
while (y != 0) {
int z = x % y;
x = y;
y = z;
}
return x;
}
}


10057761
93ms