挑战 58 ： 诡异的直角三角形周长

541h541h

挑战 58 ： 诡异的直角三角形周长

12是能围成一个整数边长的直角三角形的最小长度，能围成整数边长的直角三角形的长度还有很多：
12 : (3,4,5)
24 : (6,8,10)
30 : (5,12,13)
36 : (9,12,15)
40 : (8,15,17)
48 : (12,16,20)
相反，20就不可能是一个整数边长的直角三角形的周长。而有一些长度就不止是围成一种直角三角形了，例如120的长度能围成三种不同的直角三角形。
120 : (30,40,50), (20,48,52), (24,45,51)
假设直角三角形的周长为L，当12≤ L ≤ 150,0000，请问只能以一种方式构成整数边的直角三角形的L有多少个？

大神来解答啊啊!如何优化，这数据坑的。

rosynirvana

刚看见，纯粹的数学题
搜索“勾股数”然后就能看到关键算法

ukyo502

初等数论中相关思路~~
d:\我的文档\ahailei.png
python 代码
import time
c1=time.time()
#======================================
def gcd(a, b):
  if a < b:
    a, b = b, a
  while b != 0:
    temp = a % b
    a = b
    b = temp
  return a
#======================================
D={};count_D=0;Big=15*10**5
for x in xrange(2,int((Big/2)**0.5)):
      for y in xrange(x-1,0,-2):
            if gcd(x,y)==1:
                  L=2*x*(x+y)
                  for L1 in xrange(L,Big,L):
                        if L1 in D:
                              D[L1]+=1
                        else:
                              D[L1]=1
#==========================================
for z in D:
      if D[z]==1:
            count_D+=1
print count_D
print time.time()-c1