Project Euler 86：Cuboid route 长方体路径

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.

长方体路径

蜘蛛S位于一个6乘5乘3大小的长方体屋子的一角，而苍蝇F则恰好位于其对角。沿着屋子的表面，从S到F的最短“直线”距离是10，路径如下图所示：

但是，每个立方体都有三条可能的最短路径，而且最终的最短路径并不一定是整数。

考虑所有整数边长的立方体屋子，最大不超过M×M×M，当M=100时一共有2060个立方体的最短路径是整数，而且这也是解超过2000的最小的M；M=99时又1975个立方体的最短路径是整数。

找出解超过一百万的最小的M。

解题

可以直接求的

为了防止在计算的过程中，出现立方体重复的显现，可以假设 a<=b <=c

最短路径有三种：

path1 = (a+b)^2 + c^2

path2 = (a+c)^2 + b^2

path3 = (c+b)^2 + a^2

上面三个值展开后可以发现都含有a b c的平方项，不同项以此是：2ab 2 ac 2bc

显然的发现2ab是最小值，也就是说path1就是最小路径值，判断是不是整数就很简单了。

Java关键程序

    static void run(){
        int limit = 1000000;
        int count =0;
        int M = 1;
        for(M = 1;;M++){
//            当 a<= b <= c 最小路径就是 (a+b)*(a+b) + c*c 开根号
            for(int a = 1;a<= M ;a++){
                for(int b =a ;b<= M;b++){
                    int c = M ;
                    int path = (a+b)*(a+b) + c*c;
                    int tmp = (int)Math.sqrt(path);
                    if(tmp*tmp == path){
                        count ++;
                    }
                }
            }
            if(count> limit){
                System.out.println(M);
                break;
            }
        }
    }

另外一种方法，参考链接

同样假设:a<=b<=c

最小值是:(a+b)^2 + c^2

可以把 a+b看成一个值ab

显然ab的范围就是[2,2M]

后面就看不懂了。

上面两种放大都是固定c的值，c也是最大值，找出对应c满足条件的立方体数量，c+1的时候显然是包括c的情况的解。

package Level3;

public class PE086{
    static void run(){
        int limit = 1000000;
        int count =0;
        int M = 1;
        for(M = 1;;M++){
//            当 a<= b <= c 最小路径就是 (a+b)*(a+b) + c*c 开根号
            for(int a = 1;a<= M ;a++){
                for(int b =a ;b<= M;b++){
                    int c = M ;
                    int path = (a+b)*(a+b) + c*c;
                    int tmp = (int)Math.sqrt(path);
                    if(tmp*tmp == path){
                        count ++;
                    }
                }
            }
            if(count> limit){
                System.out.println(M);
                break;
            }
        }
    }
    static void run2() {
        int limit = 1000000;
        
        int c = 1;
        int count = 0;
        while(count < limit){
            c++;
            for(int ab = 2;ab<= 2*c;ab++){
                int path = ab*ab + c*c;
                int tmp = (int)Math.sqrt(path);
                if(tmp*tmp== path){
                    count += (ab>=c)?1+(c-(ab+1)/2):ab/2;
                }
            }
//            if(c ==100)
//                System.out.println(count);
        }
        System.out.println(c);
    }


    public static void main(String[] args){
        long t0 = System.currentTimeMillis();
        run2();
        long t1 = System.currentTimeMillis();
        long t = t1 - t0;
        System.out.println("running time="+t/1000+"s"+t%1000+"ms");

    }
}

1818
running time=0s39ms

Python 时间有点长

# coding=gbk
import time as time 

t0 = time.time()
print 3**2
print int(8**0.5) 
def run():
    limit = 1000000
    count = 0
    M = 1
    while count < limit:
        for a in range(1,M+1):
            for b in range(a,M+1):
                c = M 
                path = (a+b)**2 + c**2
                tmp = int((path)**0.5)
                if tmp**2 == path:
                    count +=1
        M += 1
        
    print M-1 
    
# 1818 
# running time= 1062.27400017 s   


run()
t1 = time.time()
print "running time=",(t1-t0),"s"