题目139：求允许斜边上的正方形镶嵌其中的毕达哥拉斯三角形

欧拉计划

Pythagorean tiles

Let (a, b, c) represent the three sides of a right angle triangle with integral length sides. It is possible to place four such triangles together to form a square with length c.

For example, (3, 4, 5) triangles can be placed together to form a 5 by 5 square with a 1 by 1 hole in the middle and it can be seen that the 5 by 5 square can be tiled with twenty-five 1 by 1 squares.

However, if (5, 12, 13) triangles were used then the hole would measure 7 by 7 and these could not be used to tile the 13 by 13 square.

Given that the perimeter of the right triangle is less than one-hundred million, how many Pythagorean triangles would allow such a tiling to take place?

题目：

令 (a, b, c) 表示一个边长皆为整数的直角三角形的三边长。可以将四个这样的三角形放在一起来形成一个边长为 c 的正方形。

例如，(3, 4, 5) 这个三角形可以形成一个 5×5 的正方形，这个正方形中间有一个 1×1 的洞。可以看出这个 5×5 的正方形可以用 25 个 1×1 的正方形来铺成。

但是，如果 (5, 12, 13) 这个三角形被用来形成正方形，那么中间的洞大小为 7×7，而 7×7 的正方形无法铺成 13×13 的正方形。

对于周长小于 1 亿的直角三角形，有多少个毕达哥拉斯三角形满足上述的“铺砖”条件？

guosl

应用本原直角三角形的性质来做。
所谓本原直角三角形指三边长度皆为整数，且两两互素的直角三角形。显然任意一个整数边长的直角三角形都是某个本原直角三角形放大得来，所以我们只要考虑计算本原直角三角形的情况，然后放大就行了。
而本原直角三角形的三条边长有计算公式：
a=m^2-n^2，b=2mn（二条直角边）
c=m^2+n^2（斜边）
其中m、n皆为正整数。同时m、n满足(1)m>n；(2)m、n互素；(3)m、n奇偶性相异。
答案：10057761

#include <iostream>
using namespace std;

int gcd(int x, int y)
{
  if (y == 0)
    return x;
  return gcd(y, x%y);
}

int main(void)
{
  int nCount = 0;
  for (long long m = 2; m <= 10000; ++m) //枚举m
  {
    for (long long n = 1; n < m; ++n) //枚举n
    {
      long long l = m + n;
      l *= 2 * m; //计算周长
      if (l >= 100000000ll)
        break;
      if (((m + n) & 1) == 0) //判断m,n的奇偶性
        continue;
      if (gcd(m, n) > 1) //判断m,n是否互质
        continue;
      long long c = m * m + n * n;//计算大正方形的边长
      long long d = 2 * m*n - m * m + n * n;//计算小正方形的边长
      if (d < 0)
        d = -d;
      if (c%d == 0) //判断是否整除
      {
        long long l1 = l;
        while (l1 < 100000000ll) //计算放大的情况
        {
          ++nCount;//计数
          l1 += l;//放大
        }
      }
    }
  }
  cout << nCount << endl;
  return 0;
}