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

主题链接：

题目大意：

求满足以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;

}