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

Almost equilateral triangles 题号:94 难度: 35 中英对照

It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the almost equilateral triangle 5-5-6 has an area of 12 square units.

We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.

Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).

Solution

设腰长为$a$,底边为$b$,底边上的高为$h$。 则考虑当$b=a+1$和$b=a-1$两种情况: 由勾股定理有: $$a^2 - h^2 = \left( \frac{a \pm 1}{2} \right) ^ 2$$ 于是化简为 $$\left( \frac{3a \pm 1}{2} \right) ^ 2 - 3 h ^ 2 = 1$$ 而根据问题66,该方程为Pell方程,有一个明显的正整数解为$(x,y)=(2,1)$,而剩下的解成为一个数列: $$ x_n = 2 x_{n-1} + 3 y_{n-1} $$ $$ y_n = x_{n-1} + 2 y_{n-1} $$ 根据该递推,直接计算在范围内的$x,y$,然后反推$a=\frac{2x \mp 1}{3}$即可求得其周长。 需要判定$a$是否为整数。

Code

public final class p94 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }	
    static public int LIMIT=1000000000;
    static public String run(){
    	long ans=0;
    	//a a a+1
    	for(long x=2,y=1;;){
    		if((2*x+1)%3==0){
    			long a=(2*x+1)/3;
	    		long C=3*a+1;
	    		if(C>LIMIT) break;
	    		ans+=C;
    		}
    		//更新xy
    		long nx=2*x+3*y;
    		long ny=x+2*y;
    		x=nx;y=ny;
    	}
    	//a a a-1
    	for(long x=2,y=1;;){
    		if((2*x-1)%3==0){
    			long a=(2*x-1)/3;
    			if(a-1>0){
		    		long C=3*a-1;
		    		if(C>LIMIT) break;
		    		ans+=C;
    			}
    		}
    		//更新xy
    		long nx=2*x+3*y;
    		long ny=x+2*y;
    		x=nx;y=ny;
    	}
    	return Long.toString(ans);
    }
}
518408346
0ms