题目地址：POJ 1305
题意：给一个整数N，求N范围内的本原的毕达哥拉斯三元组的个数，以及N以内毕达哥拉斯三元组不涉及数的个数。
思路：
首先我们先来了解一下一些基本的定义
毕达哥拉斯三元组：
设不定方程: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
所以根据定理，对于本题只要枚举一下m,n(m,n<=sqrt(n))，然后将三元组乘以i(保证i*z小于N)，就可以求出所有的毕达哥拉斯三元组。
但是注意：因为在N范围内，所以z < N，即m^2 + n^2 < N。
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <bitset>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef __int64 LL;
const int inf=0x3f3f3f3f;
const double pi= acos(-1.0);
const double esp=1e-6;
using namespace std;
const int Maxn=1e6+10;
int vis[Maxn];
int gcd(int a,int b)
{
while(b!=0){
int r=b;
b=a%b;
a=r;
}
return a;
}
int main()
{
int N;
while(~scanf("%d",&N)){
int cnt1=0;
int cnt2=0;
memset(vis,0,sizeof(vis));
int t=(int)sqrt(N*1.0);
for(int n=1;n<=t;n++){
for(int m=n+1;m<=t;m++){
if(n*n+m*m>N) break;
if((n&1)!=(m&1)){
if(gcd(n,m)==1){
int x=m*m-n*n;
int y=2*m*n;
int z=m*m+n*n;
cnt1++;
for(int i=1;;i++){
if(i*z>N) break;
vis[x*i]=1;
vis[y*i]=1;
vis[z*i]=1;
}
}
}
}
}
for(int i=1;i<=N;i++){
if(!vis[i]) cnt2++;
}
printf("%d %d\n",cnt1,cnt2);
}
return 0;
}