# poj 1305 (毕达哥拉斯三元组，构造勾股数)

Posted by 111qqz on Saturday, August 22, 2015

## TOC

***a=st,b=(s^2-t^2)/2,c=(s^2+t^2)/2

case:(3,4,5) (5,12,13) (8,15,17) (7,24,25) (20,21,29)(9,40,41)(12,35,37)(11,60,61)(28,45,53) (33,56,65) (16,63,65)

3² = 5² - 4² = (5-4)(5+4) = 1 × 9

15² = 17²-8² = (17-8)(17+8) = 9 ×25

35² = 37² - 12² = (37-12)(37+12) = 25 ×49

……

c=（s²+t²)/2, b=(s²-t²)/2,a = √(c-b)(c+b) = st.这就得出了勾股数组定理：

**
**

``````/*************************************************************************
> File Name: code/poj/1305.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年08月22日 星期六 13时49分30秒
************************************************************************/

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<stack>
#define y0 abc111qqz
#define y1 hust111qqz
#define yn hez111qqz
#define j1 cute111qqz
#define tm crazy111qqz
#define lr dying111qqz
using namespace std;
#define REP(i, n) for (int i=0;i<int(n);++i)
typedef long long LL;
typedef unsigned long long ULL;
const int inf = 0x3f3f3f3f;
const int N= 1E6+7;
bool v[N];
int n;
int gcd(int a,int b){
if (a<b) return gcd(b,a);
if (a%b==0) return b;
return gcd(b,a%b);
}
int main()
{
while (scanf("%d",&n)!=EOF){
memset(v,false,sizeof(v));
int ans = 0 ;
int cnt = 0 ;
for ( int t = 1 ; t <= n ;t = t + 2){
for ( int s = t+2 ; s*t<= n; s = s + 2){
if (gcd(s,t)==1){
int a = s*t;
int b = (s*s-t*t)/2;
int c = (s*s+t*t)/2;
if (a<=n&&b<=n&&c<=n){
ans++;
for ( int i = 1 ; i*a<=n&&i*b<=n&&i*c<=n;i++){
v[i*a] = true;
v[i*b] = true;
v[i*c] = true;
}
}
}
}
}
for ( int i = 1 ; i <= n ; i++){
if (!v[i]) cnt++;
}
printf("%d %d\n",ans,cnt);
}
return 0;
}
``````

「真诚赞赏，手留余香」