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

题意是说,能构造多少本元勾股数和勾股数,要求构造的数<=n

所谓本元勾股数,就是三个勾股数没有公因数,两两互质。

由本元勾股数扩大k倍,就可以得到其他勾股数。

而构造本元勾股数的方法如下:

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

其中s>t>=1是任意没有公因数的奇数!

引用一段构造正确性的证明:

本原勾股数组(PPT)是一个三元组(a,b,c),其中a,b,c无公因数,且满足a² +b² =c²。

很明显存在无穷多个勾股数组(abc同乘以n),下面研究abc没有公因数的情况,先写出一些本原勾股数组:

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)

观察可以看出a,b奇偶性不同且c总是奇数。(用一点技巧可以证明这是正确的)

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-b与c+b总是平方数,并且c-b与c+b木有公因数。证明一下下:假设有公因数,设d是c-b与c+b的公因数,则d也整除(c+b)+(c-b)=2c, (c+b)-(c-b) = 2b,所以d整除2c,2b,但是b,c木有公因数,又假设了(a,b,c)是本原勾股数组,从而d等于1或2,又因为d整除(c-b)(c+b)=a².a²是奇数,所以d = 1,c-b与c+b木有公因数。,又因为(c-b)(c+b)=a²,所以c-b与c+b的积是平方数,只有二者都是平方数才会出现(可以把二者分解成素数乘积直观地看出),令c+b = s²,c-b=t²,解得

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

每个本原勾股数组(a,b,c)(a为奇数,b偶数)都可由如下公式得出:a=st,b=(s²-t²)/2, c = (s²+t²)/2, 其中s>t>=1是没有公因数的奇数。

当取t=1时就可以得到上面的许多例子。

**
**

/*************************************************************************
	> File Name: code/poj/1305.cpp
	> Author: 111qqz
	> Email: rkz2013@126.com 
	> Created Time: 2015年08月22日 星期六 13时49分30秒
 ************************************************************************/
 1#include<iostream>
 2#include<iomanip>
 3#include<cstdio>
 4#include<algorithm>
 5#include<cmath>
 6#include<cstring>
 7#include<string>
 8#include<map>
 9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)  
21typedef long long LL;
22typedef unsigned long long ULL;
23const int inf = 0x3f3f3f3f;
24const int N= 1E6+7;
25bool v[N];
26int n;
27int gcd(int a,int b){
28    if (a<b) return gcd(b,a);
29    if (a%b==0) return b;
30    return gcd(b,a%b);
31}
32int main()
33{
34    while (scanf("%d",&n)!=EOF){
35	memset(v,false,sizeof(v));
36	int ans = 0 ;
37	int cnt = 0 ;
38	for ( int t = 1 ; t <= n ;t = t + 2){
39	    for ( int s = t+2 ; s*t<= n; s = s + 2){
40		if (gcd(s,t)==1){
41		    int a = s*t;
42		    int b = (s*s-t*t)/2;
43		    int c = (s*s+t*t)/2;
44		    if (a<=n&&b<=n&&c<=n){
45			ans++;
46			for ( int i = 1 ; i*a<=n&&i*b<=n&&i*c<=n;i++){
47			    v[i*a] = true;	
48			    v[i*b] = true;
49			    v[i*c] = true;
50			}
51		    }
52		}
53	    }
54	}
55	for ( int i = 1 ; i <= n ; i++){
56	    if (!v[i]) cnt++;
57	}
58	printf("%d %d\n",ans,cnt);
59    }
60	return 0;
61}