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

Cuboid route 题号:86 难度: 35 中英对照

A spider, S, sits in one corner of a cuboid room, measuring 6 by 5 by 3, and a fly, F, sits in the opposite corner. By travelling on the surfaces of the room the shortest "straight line" distance from S to F is 10 and the path is shown on the diagram.


However, there are up to three "shortest" path candidates for any given cuboid and the shortest route doesn't always have integer length.

It can be shown that there are exactly 2060 distinct cuboids, ignoring rotations, with integer dimensions, up to a maximum size of M by M by M, for which the shortest route has integer length when M = 100. This is the least value of M for which the number of solutions first exceeds two thousand; the number of solutions when M = 99 is 1975.

Find the least value of M such that the number of solutions first exceeds one million.


Solution

对边长为$a,b,c$的立方体(其中$a \leq b \leq c$)所求路径长度为$sqrt( (a+b)^2 +c^2)$,所以只需要求$(a+b)^2 +c^2$是完全平方数的所有$a \leq b \leq c$即可。 先枚举$c$,然后枚举$a+b$的值,此时$2 \leq a+b \leq 2c$,直接判断$(a+b)^2 +c^2$是否为完全平方数即可。

Code


public final class p86 {
    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 final int LIMIT=1000000;
    
    static public String run(){
    	int ans=0;
		int cnt=0;
    	for(int c=1;;c++){
    		for(int ab=2;ab<=2*c;ab++){
    			if(check_sqrt((long)ab*ab+c*c)){
    				if(ab<=c)
    					cnt+=ab/2;
    				else
    					cnt+=c-(ab+1)/2+1;
    			}
    		}
    		if(cnt>LIMIT){
    			ans=c;
    			break;
    		}
    	}
    	return Integer.toString(ans);
    }
    static public boolean check_sqrt(long a){
    	long b=(int)(Math.sqrt(a)+1e-7);
    	if(b*b==a)
    		return true;
    	return false;
    }
}
1818
33ms