FZU1669 Right-angled Triangle【毕达哥拉斯三元组】

主题链接：

http://acm.fzu.edu.cn/problem.php?pid=1669

题目大意：

求满足以a、b为直角边，c为斜边，而且满足a + b + c <= L的直角三角形的个数。

思路：

勾股定理。a、b、c也就是本原毕达哥拉斯三元组，则满足：

x = m^2 - n^2

y = 2*m*n

z = m^2 + n^2

当中m > n，且若m为奇数，则n为偶数。若m为偶数。则n为奇数。

枚举m、n，然后将三元组乘以i倍。保证 i * (x + y + z)在所给范围内(2 * m^2 + 2 * m*n <= L)，

就能够求出全部满足条件的三元组。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

bool flag[1001000];

int GCD(int a,int b)
{
    if(b == 0)
        return a;
    return GCD(b,a%b);
}

int main()
{
    int N;
    while(cin >> N)
    {
        int temp,m,n,i,ans,x,y,z;
        ans = 0;
        memset(flag,false,sizeof(flag));
        temp = sqrt(N*1.0);
        for(n = 1; n <= temp; ++n)
        {
            for(m = n+1; m <= temp; ++m)
            {
                if(2*m*m + 2*m*n > N)
                    break;
                if((n&1) != (m&1))
                {
                    if(GCD(m,n) == 1)
                    {
                        x = m*m - n*n;
                        y = 2*m*n;
                        z = m*m + n*n;
                        for(int i = 1; ; ++i)
                        {
                            if(i*(x+y+z) > N)
                                break;
                            ans++;
                        }

                    }
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}