第九日 特殊的毕达哥拉斯三元组

一个毕达哥拉斯三元组是三个自然数的集合, a < b < c, 其中,
a2 + b2 = c2

比如, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.
只存在一个毕达哥拉斯三元组 ，其中a + b + c = 1000.
求abc的积

分析：
a+b+c=1000
=> (a+b+c)^2 = 10^6
=>a^2+b2+c^2+2(ab+ac+bc) = 10^6
又因为a2 + b2 = c2
=>2(c^{2+ab+ac+bc)=10}6
=> 2( (c+a+b)c+ab )=10^6
=>2(1000c+ab)=10^6
=>c = ((10^6 /2)- ab)/1000
代入a+b+c=1000得
((10^6 /2)- ab)/1000+a+b=1000

=> 1000(a+b)=500000+ab -----------等式A
算法应该在[1,999]内遍历满足等式A的a和b

另外，等式两边同时除以1000后 ，
由于左边的a+b是整数，右边ab/1000必然也是整数
ab/1000=n =>ab = 1000n
所以a和b的尾数不可能是1 3 7 9，同时两个数的尾数不可能都为5，
所以可以统一假设a的尾数不可能是1 3 5 7 9，也就是a是偶数

又因为 a<b且a+b+c=1000，所以a+b<1000,即a<500

从等式A又能看出a+b>500,即b>500-a

answer =  a*b*(1000-a-b)
  where (a,b) = head [(a,b) | a<-[2,4..498],b<-[500-a+1..1000-a],a*b `mod` 1000  ==0,1000*(a+b)==500000+a*b ]

31875000