094. 几乎等边三角形(Almost equilateral triangles)

很容易证明不存在边长与面积都为整数的等边三角形，然而几乎等边的三角形如\((5,5,6)\)的面积为\(12\)是一个整数。我们可以把几乎等边的三角形定义为两条边相等，而另一边最多和它们相差一个单位的三角形。

求所有的边长和面积都为整数，且周长不超过十亿的几乎等边三角形的周长之和。

分析：题目把几乎等边三角形定义为两边相等，而另一边最多和它们相差一个单位的三角形。显然这种三角形是一个等腰三角形，而另一边要不比这两边大一、要不比这两边小一。假设我们设相等的两条边的长度为\(a\)，则第三边的长度\(b=a\pm1\)。如下图所示：

过点\(A\)作\(BC\)的垂线\(AD\)，因为是一个等腰三角形，所以\(AD\)也是边\(BC\)的中垂线，\(D\)是\(BC\)的中点。则根据勾股定理易知：

因为三角形的面积\(S_{\bigtriangleup ABC}=by/2\)，所以要让三角形面积为整数，\(y\)也必须为整数。因此我们的问题转化为求上述方程的正整数解。每找到一组正整数解，就对应一个几乎等边三角形，从而可以求出他们的周长并求和。为了解这个不定方程，我们需要对其进行一些变换，首先在左右两侧同时乘以十二：

再在方程两边同时加上四：

再在方程两边同时除以四：

我们令\(x=(3a\pm1)/2\)，则原方程转化为：

显然这是我们在第六十六题中讨论过的佩尔方程。只要我们找到方程的一组正整数解\((x,y)\)，就可以反向推出三角形边长\(a=(2x\pm1)/3\)，面积\(S=(a\pm1)\cdot y/2\)。只要\(a\)与\(S\)都为整数，我们就找到了一个符合要求的几乎等边三角形，易知其周长\(p=3a\pm1\)。

易知上述佩尔方程的最小正整数解为\((x=2,y=1)\)，从而可以推出\(a=1\)(另一个解不是整数)，则三条边分别是\((1,1,2)\)，不符合三角形两边之和必然大于第三边的要求，所以这不是一个符合要求的解。我们知道对于佩尔方程，如果我们找到了它的最小正整数解\((x_1,y_1)\)，则该方程其它的解满足以下递推关系：

则对于上述佩尔方程有：

因此我们可以得到递推关系：

根据上述递推关系，我们可以找到这个佩尔方程的无穷多组正整数解，如将\((x_1=2,y_1=1)\)代入，可以得到\((x_2=7,y_2=4)\)，从而可以找到一个整数解\(a=(2\times7+1)/3=5\)，正是题目中给出的例子。我们从这组解开始根据递推关系向上寻找正整数解，再计算出相应的边长和面积，判断两者是否为整数，如果均为整数则计算出相应周长并累加起来。当周长超过十亿时停止计算，得到的符合要求的几乎等边三角形的周长之和了。代码如下：

# time cost = 25.1 µs ± 56.2 ns

def main(U=10**9):
    x,y = 7,4
    p_sum = 0
    while True:
        a1,a2 = (2*x+1)/3,(2*x-1)/3
        s1,s2 = (a1+1)*y/2,(a2-1)*y/2
        p1,p2 = (3*a1+1),(3*a2-1)
        if (p1<=U) and (a1%1==0) and (s1%1==0):
            p_sum += p1
        if (p2<=U) and (a2%1==0) and (s2%1==0):
            p_sum += p2
        if (p1>U) and (p2>U):
            return p_sum
        else:
            x,y = 2*x+3*y,x+2*y