039. 整数直角三角形(integer right triangles)

如果\(p\)是一个整数边\(\{a,b,c\}\)的直角三角形的周长,对于\(p=120\)仅有三个符合要求的解:

$$ \{20,48,52\},\{24,45,51\},\{30,40,50\} $$
求使得符合要求的解的数量最大的\(p\)值,其中\(p\le1000\)

分析:此题的解题思路相对直接,据题意我们有\(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\le 1000\)时满足条件的勾股三元数对最多的\(p\)值,则我们只需要把不同的\(p\)代入上面的函数,算出对应的勾股数对的数量,最后统计勾股数对最多的对应周长即可。但考虑到题目的性质,我们可以对需要筛选的\(p\)值范围再做精减,假设:

据此,我们可以得出结论:\(p\)必然为一个偶数,则我们只需要筛选1000以下的所有偶数周长即可,缩小了一半的筛选范围。

def number_of_solution(p):
    num = 0
    for a in range(1,p//3):
        if (p**2-2*p*a)%(2*p-2*a) == 0:
            num += 1
    return num

def main(n=1000):
    d = {p:number_of_solution(p) for p in range(2,n+1,2)}
    ans = max(d,key=d.get)
    return ans