075. 唯一整数直角三角形(Singular integer right triangles)

把一根线弯折成直角三角形,这个直角形的每条边都是整数,并且弯折的方法仅有一种,满足以上条件的最小的线的长度是十二,如下长度也满足这个性质:

$$ \begin{aligned} &12:(3,4,5)\\ &24:(6,8,10)\\ &30:(5,12,13)\\ &36:(9,12,15)\\ &40:(8,15,17)\\ &48:(12,16,20) \end{aligned} $$
相反,有些长度比如说20就无法将其弯折成整数直角三角形,而另有一些长度却可以弯折成多个整数直角三角形,比如对于长度为120的线条可以弯折成三个整数直角三角形:
$$ 120:(30,40,50), (20,48,52), (24,45,51) $$
给它长度\(L\)\(L\le1,500,000\),仅能形成一个整数直角三角形的\(L\)数量是多少?

分析:和这道题类似的题目,我们之前已经碰到过两次,分别是第九题和第三十九题,都涉及到求解在给定周长的情况下,满足条件的整数直角三角形的解的个数。在第九题中,我们给出了两种解题思路,一种是基于变量代换并利用整除性质的方法,另一种则是利用欧几里德公式的思路。对于这道题我们仍然可以尝试这两种思路,事实表明第一种思路由于效率太低已经无法在要求时间内得到答案,所以只能采用第二种思路。

回忆一下欧几里德公式,假设\(m>n>0,gcd(m,n)=1\)\(m,n\)不都为奇数,则\(m,n\)可以通过欧几里德公式形成一个本原勾股三元数\((a,b,c)\),其中\(a,b,c\)两两互质,\(a\)为长的直角边,\(b\)为短的直角边,\(c\)为斜边,则有:

$$ a=m^2-n^2,\ b=2mn,\ c=m^2+n^2 $$

对本原勾股三元数的三个元素同时乘以\(k(k\ge1)\),形成的三元数\((ka,kb,kc)\)也是勾股三元数。通过以上公式,易知勾股三元数的周长为:

$$ p=ka+kb+kc=k(a+b+c)=2km(m+n) $$

因此我们只要得到了一组本元勾股三元数的周长,就可以得到其它勾股三元数的周长。据此我们可以列出所有周长小于特定值的勾股三元数,知道某个特定周长对应几个勾股三元数,我们关心是的那些只有一组勾股三元数的周长的个数。据题意,周长最大只能为一百五十万且\(m<m+n\),则有:

$$ 2km(m+n)\le1500000\Rightarrow m\le \sqrt{1500000/2k}\le \sqrt{1500000/2}=\sqrt{750000}\approx866 $$

则我们可以据此搜寻范围内的\((m,n)\)值,计算相应的整数直角三角形的周长,并计算各个周长出现的次数,返回只出现了一次的周长的个数,即为题目所求。

# time cost = 720 ms ± 18.5 ms

from math import gcd
from collections import Counter

def main(N=1500000):
    limit,arr = int((N//2)**0.5)+1,[]
    for m in range(2,limit):
        for n in range(1,m):
            if (m+n)%2 == 1 and gcd(m,n) == 1:
                p,k = 2*m*(m+n),1
                while k*p <= N:
                    arr.append(k*p)
                    k += 1
    c = Counter(arr)
    return len([x for x in c.values() if x==1])