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

Right-angled triangles that share a cathetus 题号:176 难度: 70 中英对照

The four right-angled triangles with sides (9,12,15), (12,16,20), (5,12,13) and (12,35,37) all have one of the shorter sides (catheti) equal to 12. It can be shown that no other integer sided right-angled triangle exists with one of the catheti equal to 12.

Find the smallest integer that can be the length of a cathetus of exactly 47547 different integer sided right-angled triangles.

Solution

根据勾股定理,设所求直角边为$a$,另外两边为$b,c$,则有$a^2=(b-c)(b+c)$。 注意到$b-c$和$b+c$奇偶性相同,则: 若$a$为偶数,解的数量为$\left( a/2\right) ^2$的约数个数 减一再除以2。 若$a$为奇数,解的数量为$\left( a\right) ^2$的约数个数 减一再除以2。 将数$n$因式分解为$n=\prod_i p_i^{r_i}$,约数个数为$d(n)=\prod_i \left( r_i+1\right)$。 此处$n=a^2$或$n=\left( a/2\right) ^2$,是个完全平方数,则所有的$r_i$都是偶数,$d(n)$一定是奇数。 所以相当于求解$d(n)=47547\times 2+1$的最小平方数$n$,所求$a=sqrt(n)*2$。 而$d(n)=47547\times 2+1$的素因子分解为$5,7,11,13,17$,次数均为$1$,则将 $3,6,10,12,16$依次安放至$2,3,5,7,11$的指数,即可得到最小的数$n$。

Code

import java.util.ArrayList;

public final class p176 {
    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 final int prime[]=new int[]{2,3,5,7,11,13,17,19,23};
	
	static public String run() {
		final long x=47547;
		return ""+solve(x);
    }
    
	static long solve(long x){
		long d=x*2+1;
		ArrayList<Integer> ps=new ArrayList<Integer>();
		long tmp=d;
		for(int i=0;i<prime.length;i++){
			if(tmp%prime[i]==0)
				ps.add((prime[i]-1)/2);
		}
		long num=1;
		for(int i=0;i<ps.size()&&i<prime.length;i++){
			for(int j=0;j<ps.get(i);j++)
				num*=prime[ps.size()-1-i];
		}
		return num*2;
	}
	
	
}
96818198400000
0ms