首页 > 代码库 > POJ 1305

POJ 1305

求本原毕达三原组的个数以及不是毕达三元组的数。

 

这道题需要把规模降下来,由

x=m^2-n^2

y=2mn

z=m^2+n^2

由有x+y<=2*k即(m+n)^2<2k开方后即可把m,n范围缩小,然后枚举

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int Maxn=1000010;bool flag[Maxn];int gcd(int a,int b){	if(b==0) return a;	return gcd(b,a%b);}void slove(int n){	int x,y,z;	int count=0;	memset(flag,false,sizeof(flag));	int t=(int)sqrt(n*2.0);	for(int i=1;i<=t;i++){		for(int j=i+1;j<=t;j++){			if(i*i+j*j>n) break;			if(2*i*j>n) break;			if(i%2!=j%2){				if(gcd(i,j)!=1) continue;				x=j*j-i*i;				y=2*i*j;				z=i*i+j*j;				count++;				flag[x]=flag[y]=flag[z]=true;				for(int k=2;;k++){					if(z*k>n) break;					flag[x*k]=flag[y*k]=flag[z*k]=true;				}			}		}	}	int ac=0;	for(int i=1;i<=n;i++)	if(!flag[i]) ac++;	printf("%d %d\n",count,ac);}int main(){	int n;	while(scanf("%d",&n)!=EOF){		slove(n);	}	return 0;}

  

POJ 1305