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

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

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int gcd(int x, int y)
   
5. {
   
6.   if (y == 0)
   
7.     return x;
   
8.   return gcd(y, x%y);
   
9. }
   
10. 
    
11. int main(void)
    
12. {
    
13.   int nCount = 0;
    
14.   for (long long m = 2; m <= 10000; ++m) //枚举m
    
15.   {
    
16.     for (long long n = 1; n < m; ++n) //枚举n
    
17.     {
    
18.       long long l = m + n;
    
19.       l *= 2 * m; //计算周长
    
20.       if (l >= 100000000ll)
    
21.         break;
    
22.       if (((m + n) & 1) == 0) //判断m,n的奇偶性
    
23.         continue;
    
24.       if (gcd(m, n) > 1) //判断m,n是否互质
    
25.         continue;
    
26.       long long c = m * m + n * n;//计算大正方形的边长
    
27.       long long d = 2 * m*n - m * m + n * n;//计算小正方形的边长
    
28.       if (d < 0)
    
29.         d = -d;
    
30.       if (c%d == 0) //判断是否整除
    
31.       {
    
32.         long long l1 = l;
    
33.         while (l1 < 100000000ll) //计算放大的情况
    
34.         {
    
35.           ++nCount;//计数
    
36.           l1 += l;//放大
    
37.         }
    
38.       }
    
39.     }
    
40.   }
    
41.   cout << nCount << endl;
    
42.   return 0;
    
43. }

复制代码