最素勾股三元组.cpp

列出最素勾股三元组的前10万项。（竞赛专用

#include<iostream.h> 
#include<fstream.h>
#include<sstream>
#include<time.h>
#include<math.h>

int  x=3,y=4,z=0;
int  m=0,n=0,count=1,k=1;
int  v[100001][3];

int  GCD(int x,int y)   
{   
	int m,n,t;   
	if(x>y)   
	{   
		m=x;   
		n=y;   
	}   
	else   
	{   
		m=y;   
		n=x;   
	}   
	while(m%n!=0)   
	{   
		t=n;   
		n=m%n;   
		m=t;   
	}    
	return n;   
} 
void go(int maxsize)
{ 
	int m,n,t,i;
    while(count<=maxsize)
		{
			if(x%2==1)            
			{
				t=0.7*sqrt(x);
				if(t%2==1) i=t;
				else i=t+1;
				for(;i>=1;i-=2)
				{
					if(x%i==0)
					{
						m=(x/i+i)/2;
						n=(x/i-i)/2;
						y=m*n*2;
						if(x<y&&GCD(x,y)==1)
						{	
					        v[count][0]=x;
							v[count][1]=y;
							v[count][2]=m*m+n*n;
							count++;
							if(count>maxsize) break;			
						}
					}
				}
			}	
			else
			{ 
				if(x%4==0)
				{
					for(n=0.45509*double(sqrt(x));n>0;n-=1)
					{
						if(x%(2*n)==0)
						{
							m=x/2/n;
							y=m*m-n*n;
							if(x<y&&GCD(x,y)==1)
							{
								v[count][0]=x;
								v[count][1]=y;
								v[count][2]=m*m+n*n;
								count++;
							}
						}
					}
				}
			}
		x++;
		}	
}
void main()
{	
	memset(v,0,sizeof(v));
	go(100000);
	ifstream read("d:\\in.txt",ios::in||ios::nocreate);
	ofstream write("d:\\out.txt",ios::out);
	while(read>>k)
		write<<v[k][0]<<" "<<v[k][1]<<" "<<v[k][2]<<endl;
	read.close();
	write.close();
}