pythagorean triples.cpp

数值分析中常用的几种算法的实现

#include<stdio.h>
#include<math.h>
int tr[100000][3];//2uv,u^2-v^2,u^2+v^2
//
int gcd(int a,int b)
{
	if(b==0)
		return a;
	return gcd(b,a%b);
}
int abs(int x)
{
	if(x>0)
		return x;
	else
		return -1*x;
}
int main()
{
	int x,y,z,u,v,i,j,n;
	int all=0;
	for(x=3;;x++)
	{
		if(x%2==0)
		{
			for(v=sqrt(x/2);v>=1;v--)
			{
				if(x%(2*v)==0)
				{
					u=x/(2*v);
					if(u<v)
						continue;
					if((u-v)%2==0)
						continue;
					if(u*u-v*v<2*v*u)
						continue;
					if(gcd(u,v)!=1)
						continue;
					tr[all][0]=x;
					tr[all][1]=u*u-v*v;
					tr[all][2]=u*u+v*v;
					all++;
				}
			}
		}
		else
		{
			for(i=sqrt(x);i>=1;i--)
			{
				if(x%i==0)
				{
					j=x/i;
					if((i+j)%2!=0||(i-j)%2!=0)
						continue;
					u=(i+j)/2;
					v=(abs(i-j)/2);
					if((u-v)%2==0)
						continue;
					if(2*u*v<u*u-v*v)
						continue;
					if(gcd(u,v)!=1)
						continue;
					tr[all][0]=u*u-v*v;
					tr[all][1]=2*u*v;
					tr[all][2]=u*u+v*v;
					all++;
				}
			}
		}
		if(all>=100000)
			break;
	}
	while(scanf("%d",&n)!=EOF)
	{
		printf("%d %d %d\n",tr[n-1][0],tr[n-1][1],tr[n-1][2]);
	}
}