poj1305(毕达哥拉斯)

毕达哥拉斯)"/>

poj1305(毕达哥拉斯)

题目链接：=1305；

题目大意：给一个正整数n求解，求解n的范围内gcd值为1的勾股数和不是勾股数的个数。

题目分析：根据毕达哥拉斯定理，gcd值为1的勾股数就是本源毕达哥拉斯三元组，有公式如下：

x=j*j-i*i;

y=2*i*j;

z=i*i+j*j;

其中i和j其中一个为奇数，另一个为偶数，且j>i;

本题数量小，直接暴力枚举就好

代码如下：

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <vector>
#include <string>
#include <utility>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <functional>using namespace std;bool flag[1000000];
int gcd(int a,int b){return (b==0)?a:gcd(b,a%b);
}
int main(){int n;while(scanf("%d",&n)!=EOF){memset(flag,false,sizeof(flag));int m=0;int x,y,z;for(int i=1;i*i<=n;i++){for(int j=i+1;j*j<=n;j++){if(i*i+j*j>n)break;if((i&1)!=(j&1)){if(gcd(i,j)==1){x=j*j-i*i;y=2*i*j;z=i*i+j*j;m++;for(int k=1;;k++){if(k*z>n)break;flag[k*x]=flag[k*y]=flag[k*z]=true;}}}}
//            cout<<i<<" ";}int k=0;for(int i=1;i<=n;i++)if(flag[i])k++;//set太慢printf("%d %d\n",m,n-k);}return 0;
}