009. 特殊的毕达哥拉斯三元数(Special Pythagorean triplet)

毕达哥拉斯三元数是指一类三个自然数的集合,其中\(a<b<c\)\(a^2+b^2=c^2\),例如\(3^2+4^2=5^2\)。仅存在一组毕达哥拉斯三元数使得\(a+b+c=1000\),求\(abc\)

分析:此题至少有两种解题思路,第一种思路如下:为了让解题思路更加一般化,设三角形的周长为\(p\),则有\(a+b+c=p\),故\(c=p-a-b\),则有:

$$ a^2+b^2=c^2=(p-a-b)^2=p^2+a^2+b^2-2pa-2pb+2ab $$

则可以得到:

$$ b=(p^2-2pa)/(2p-2a) $$

则使得\(b\)为整数的\(p\)\(a\)都可以满足题目的要求,从而可以得到一组符合要求勾股三元数。此外,不失一般性,我们假设\(a\le b<c\),又因为\(a+b+c=p\),则应有\(a<p/3\),这可以缩小我们需要筛选的数\(a\)的范围。因为题目已经说明在\(p=1000\)时只存在一组勾股三元数,则我们只需要编写一个函数寻找一个合适的\(a\)值使得\(b\)为整数,一旦找到就可以计算\(c\)并返回三者的乘积。

第二种思路需要用到欧几里德公式,对于\(m>n>0\),我们知道以下三个数可以构成勾股三元数:

$$ a=k(m^2-n^2),b=2kmn,c=k(m^2+n^2) $$

则有:

$$ a+b+c=k(m^2-n^2+2mn+m^2+n^2)=k(2m^2+2mn)=2km(m+n)=1000 $$

则我们可以得到\(m(m+n)=500/k\),显然\(m<m+n\),同时\(m,n\)都是\(500/k\)的因数,则我们可以得到\(m<\sqrt{500/k}\)。同时我们有\(n=500/k\cdot m-m<m\),则有\(m>\sqrt{250/k}\),即我们可以是得到\(m\)的取值范围是\([\sqrt{250/k},\sqrt{500/k}]\)。现在我们假设\(k=1\),则\(m\in[15.81,22.36]\),这其中的整数只有16,17,18,19,20,21,显然只有20是500的因子,则有\(m=20,n=5\),则有:

$$ a=20^2-5^2=375,b=2\times20\times5=200,c=20^2+5^2=425 $$

\(a,b,c\)三者相乘即为题目所求。显然第二种思路可以直接笔算出结果,所以这里我们只列示第一种思路的代码:

def main(p=1000):
    for a in range(1,p//3):
        n,d = p**2-2*p*a,2*p-2*a
        if n % d == 0:
            b = n/d
            c = p-a-b
            return int(a*b*c)