POJ 1305 Fermat vs. Pythagoras （毕达哥拉斯三元组）

设不定方程: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=;

int n;

int vis[+];

int gcd(int a,int b){

    return b==?a:gcd(b,a%b);

}

int main()

{

    while(scanf("%d",&n)!=EOF){

        memset(vis,,sizeof(vis));

        int m=sqrt((double)n);

//printf("%d\n",m);

        int ans=; //本原的毕达哥拉斯三元组的个数

        int x,y,z;

        int a,b,d;

        for(int i=;i<=m;i+=){

            for(int j=;j<=m;j+=){

                a=max(i,j);

                b=min(i,j);

                d=gcd(a,b);

//printf("a:%d b:%d\n",a,b);

                if(d==){

                    x=a*a-b*b;

                    y=*a*b;

                    z=a*a+b*b;

                    for(int k=;k*z<=n;k++){

                        vis[x*k]=;

                        vis[y*k]=;

                        vis[z*k]=;

//printf("%d %d %d\n",x*k,y*k,z*k);

                    }

                    if(z<=n)

                        ans++;  //还应该判断最初的z是否<=n，才能ans++

                }

            }

        }

        int cnt=;//所有毕达哥拉斯三元组不涉及的数的个数

        for(int i=;i<=n;i++){

            if(!vis[i])

                cnt++;

        }

        printf("%d %d\n",ans,cnt);

    }

    return ;

}