题目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。

jerryxjr1220

1818
[Finished in 1.4s]

from math import sqrt
s = i = 0
while True:
        i += 1
        for q in range(2,2*i+1):
                n = i**2+q**2
                if sqrt(n) % 1 ==0:
                        s += (q//2 - max(1, q-i) + 1)
                if s > 10**6:
                        print i
                        exit()

fc1735

total = 0

for a in range(9999999999999999):
  for b in range(2, 2 * a + 1):
    c = int((a ** 2 + b ** 2) ** 0.5)
    if a ** 2 + b ** 2 == c ** 2:
      total += b // 2
      total -= max(b - a - 1, 0)
  if total > 1000000:
    print(a)
    break

https://github.com/devinizz/project_euler/blob/master/page02/86.py