poj1305 Fermat vs. Pythagoras----勾股数
#include<iostream>#include<cstdlib>#include<stdio.h>#include<math.h>#include<memory.h>using namespace std;#define N 1000010bool flag[N];int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b);}int main(){ int n; while(scanf("%d",&n)!=EOF) { memset(flag,false,sizeof(flag)); int ans=0; int temp=sqrt(n+0.0); for(int i=1;i<=temp;i++) { for(int j=i+1;j<=temp;j+=2) { if(i*i+j*j>n) break; if(gcd(i,j)==1) { /*if(flag[j*j-i*i]&&flag[2*j*i]&&flag[j*j+i*i]) ; else { flag[j*j-i*i]=true; flag[2*j*i]=true; flag[j*j+i*i]=true; ans++; }*/ int x,y,z; x=j*j-i*i;y=2*j*i;z=j*j+i*i; ans++; for(int k=1;;k++) { if(k*z>n) break; flag[k*x]=true;flag[k*y]=true;flag[k*z]=true; } } } } int ans2=0; for(int i=1;i<=n;i++) if(flag[i]==false) ans2++; cout<<ans<<" "<<ans2<<endl; }}
