主题链接：
pid=1669">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;
}
版权声明：本文博主原创文章。博客，未经同意不得转载。