设不定方程:x^2+y^2=z^2
若正整数三元组(x,y,z)满足上述方程，则称为毕达哥拉斯三元组。
若gcd(x,y,z)=1，则称为本原的毕达哥拉斯三元组。
定理：
正整数x,y,z构成一个本原的毕达哥拉斯三元组且y为偶数,当且仅当存在互素的正整数m,n(m>n),其中m,n的奇偶性不同,
并且满足
x=m^2-n^2,y=2*m*n, z=m^2+n^2
本题目让你求的是，在n范围内(x,y,z<=n)本原的毕达哥拉斯三元组的个数，以及n以内且毕达哥拉斯三元组不涉及的数的个数。
举个样例：
25
本原的三元组有:(3,4,5),(7,24,25),(5,12,13),(8,15,17)，即第一个要输出的为4
所有的毕达哥拉斯三元组，除了上述4个外，还有:(6,8,10),(9,12,15),(12,16,20),(15,20,25)
不包含在这些三元组里面的<=n的数有9个。
思路：很显然，依据前面给出的定理，只要枚举一下m,n(m,n<=sqrt(n))，然后将三元组乘以i（保证i*z在范围内即可），
就可以求出所有的毕达哥拉斯三元组。
#include <iostream> #include <cstdio> #include <string.h> #include <algorithm> #include <math.h> using namespace std; const int maxn=1000; int n; int vis[1000000+5]; int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } int main() { while(scanf("%d",&n)!=EOF){ memset(vis,0,sizeof(vis)); int m=sqrt((double)n); //printf("%d ",m); int ans=0; //本原的毕达哥拉斯三元组的个数 int x,y,z; int a,b,d; for(int i=1;i<=m;i+=2){ for(int j=2;j<=m;j+=2){ a=max(i,j); b=min(i,j); d=gcd(a,b); //printf("a:%d b:%d ",a,b); if(d==1){ x=a*a-b*b; y=2*a*b; z=a*a+b*b; for(int k=1;k*z<=n;k++){ vis[x*k]=1; vis[y*k]=1; vis[z*k]=1; //printf("%d %d %d ",x*k,y*k,z*k); } if(z<=n) ans++; //还应该判断最初的z是否<=n，才能ans++ } } } int cnt=0;//所有毕达哥拉斯三元组不涉及的数的个数 for(int i=1;i<=n;i++){ if(!vis[i]) cnt++; } printf("%d %d ",ans,cnt); } return 0; }