欧拉项目 | 75题 | 整数直角三角形

75题链接

给定一个整数L，可能可以弯成一个各边都是整数的直角三角形，也可能不可以。如果可以的话，可能只有一种方法，也可能有多种。
比如12，可以组成一个三边都是整数的直角三角形，且只能组出来一个。
比如10，无法弯出一个各边都是整数的直角三角形。
再比如120，有多种组合(30,40,50), (20,48,52), (24,45,51)。

L ≤ 1,500,000，有多少个L恰好有唯一一种方法得到直角三角形。

和Project Euler的很多题目一样，1500000这个值很大，暴力的遍历每个L，然后切分成三段，三段又恰好是直角三角形，这种方法时间复杂度极大，显然不可行。
另辟蹊径，我们先想办法找到所有的周长小于MaxL的直角三角形，然后遍历这些三角形，用一个map记住周长出现的次数，最后统计一次的个数即可。
现在的问题就是如果找到直角三角形呢？三边其实就是方程x^2 + y^2 = z^2的整数解。

现在万事俱备，就差coding了。

var triangles = new List<long>();
for (long a = 1; a < L / 2; a += 2)
{
    for (long b = a + 2; a * b < L / 2; b += 2)
    {
        if (Utils.GetGcd(a, b) == 1)
        {
            for (long k = 1; k * a * b < L / 2; k++)
            {
                long x = k * a * b;
                long y = k * (b * b - a * a) / 2;
                long z = k * (b * b + a * a) / 2;
                if (x + y + z <= L)
                {
                    triangles.Add(x+y+z);
                }
            }
        }
    }
}

var countMapping = new Dictionary<long, int>();
for (int i = 1; i <= L; i++)
{
    countMapping[i] = 0;
}

foreach (var circumference in triangles)
{
    countMapping[circumference]++;
}

return countMapping.Count(p => p.Value == 1);