12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)
In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.
120 cm: (30,40,50), (20,48,52), (24,45,51)
Given that L is the length of the wire, for how many values of L 1,500,000 can exactly one integer sided right angle triangle be formed?
Note: This problem has been changed recently, please check that you are using the right parameters.
下面是java解题方法：
public static void main(String[] args) {
Map<Integer, ABC> dict = new HashMap<Integer, ABC>();
int L = 1500000;
int M = (int)Math.sqrt(L / 2);
for (int m = 1; m <= M; m++) {
for (int n = 1; n < m; n++) {
int a = m * m - n * n;
int b = 2 * m * n;
int c = m * m + n * n;
int l = a + b + c;
int k = L / l;
for (int i = 1; i <= k; i++) {
int[] abc = { i * a, i * b, i * c };
Arrays.sort(abc);
check(i, l, abc, dict);
}
}
}
int count = 0;
for (ABC abc : dict.values()) {
count += abc.got;
}
System.out.println(count);
}
private static void check(int i, int l, int[] abc, Map<Integer, ABC> dict) {
int ll = i * l;
ABC tmp = dict.get(ll);
if (tmp != null) {
if (tmp.got == 1) {
int[] tmp1 = tmp.abc;
for (int x = 0; x < 3; x++) {
if (tmp1[x] != abc[x]) {
tmp.got = 0;
break;
}
}
}
} else {
dict.put(ll, new ABC(abc));
}
}
static class ABC {
public ABC(int[] abc) {
this.abc = abc;
}
int got = 1;
int[] abc;
}
这个解法的时间在秒级，解法利用了下面勾股数的性质：
1，通过a = m^2 − n^2, b = 2mn, c = m^2 + n^2 （1）可以生成所有的素勾股数和一部分派生勾股数（a,b,c）,其在（m>n,m,n为正整数）;
2,勾股数分为素勾股数和派生勾股数，而且所有派生勾股数都是由素勾股数派生而来的;
3,根据1,2,利用式（1），遍历m，n并加上派生规则可以生成所有勾股数。
注：正整数a,b,c满足a^2+b^2=c^2<=>(a,b,c)是勾股数，如果(a,b,c)=1(即a,b,c互素)，则(a,b,c)称为素勾股数,对于整数k，(ka,kb,kc)是由(a,b,c)派生的勾股数。