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

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?


Solution

毕达哥拉斯三元数定理:每个本原勾股数组(a,b,c)(a为奇数,b偶数)都可由如下公式得出 存在s > t > 0且s和t是互质的奇数使得$$a=s * t$$$$b=\frac{s^{2}-t^{2}}{2}$$$$c=\frac{s^{2}+t^{2}}{2}$$ 由该方式组成的大正方形中间的洞的边长为b - a 那么,若是大正方形可由若干个洞组成的话,大正方形的边长c必须能整除b - a 对一个满足条件的三元数(a,b,c),存在正整数k使得 ( ka , kb , kc ) 也满足条件,所以找到每找到一个(a,b,c),相当于找到了LIMIT/(a+b+c)个满足条件的毕达哥拉斯三元数

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