令$\Delta ABC$为一每个内角都小于120度的三角形，取三角形内的任意一点X，并分别记XA、XB、XC的长度为p、q、r。

费马曾向托里拆利提出挑战，要求其找到令$p+q+r$最小的点X。

托里拆利则证明了若在$\Delta ABC$的三边上分别构造等边三角形$\Delta OAB$、$\Delta NBC$和$\Delta MAC$，则这三个三角形的外接圆将交于三角形内的一点T，该点也被称为托里拆利点或费马点，即能使$p+q+r$最小的点。

不仅如此，此时还有$AN=BM=CO=p+q+r$，且AN、BM和CO也交于T点。

将$TA$、$TB$、$TC$的长度分别记作$p^*$、$q^*$、$r^*$，若$a, b, c, p^*, q^*, r^*$均为正整数，则称$\Delta ABC$为托里拆利三角形。例如，$a=399$，$b=455$，$c=511$就是一个托里拆利三角形，此时$p^*+q^*+r^*=784$。

对所有满足$p^*+q^*+r^*\le 120000$的托里拆利三角形，求所有不同的$p^*+q^*+r^*$的值之和。

本题难度:

解答

T与ABC连线所形成的三个夹角都是120度，因此由余弦定理可得 $$(p^*)^2+(q^*)^2+p^*q^*=b^2, \quad (p^*)^2+(r^*)^2+p^*r^*=c^2, \quad (q^*)^2+(r^*)^2+q^*r^*=a^2.$$ 因此需要找到能令$(p^*)^2+(q^*)^2+p^*q^*$、$(p^*)^2+(r^*)^2+p^*r^*$、$(q^*)^2+(r^*)^2+q^*r^*$均为完全平方数的$p^*,q^*,r^*$。

根据此帖的内容，满足 $$u^2+v^2+uv=w^2$$ 的本原（即$\gcd(u,v,w)=1$）三元组$(u,v,w)$可以由互素且差不被3的整除的数对$(m,n)$用以下方式 $$u=m^2-n^2, \quad v=2mn+n^2, \quad w=m^2+n^2+mn$$ 生成。

用这一方法生成所有的$p^*,q^*,r^*$并按其和$p^*+q^*+r^*$去重（满足要求的三元组共有508组，其中有些的和是重复的）即可得结果$30758397$。

注：以下代码为Python3，因Python2中无math.gcd函数。(Python2中可以使用fractions.gcd)

import math

d={}
for m in range(2,350):
    for n in range(1,m):
        if math.gcd(m,n)==1 and (m-n)%3>0:
            a,b=m*m-n*n,2*m*n+n*n
            a,b=min(a,b),max(a,b)
            k=1
            while (a+b)*k < 120000:
                if a*k in d:
                    d[a*k].add(b*k)
                else:
                    d[a*k]=set([b*k])
                k+=1
print(len(d))

s=set()
for p in d:
    for q in d[p]:
        if q in d:
            for r in d[q] & d[p]:
                if p+q+r<=120000:
                    s.add(p+q+r)

print(sum(s))