首页 > 代码库 > 勾股数组【学习笔记】

勾股数组【学习笔记】

本原勾股数组(简写为PPT)是一个三元组(a,b,c),其中a,b,c没有公因数,且满足技术分享。例如下面是一项本原勾股数组:

(3,4, 5),(5,12,13),(8,15,17),(7,24,25),(9,40,41),(11,60,61),(28,45,56),(33,56,65)。

由这个短表容易得到一些结论,例如,似乎a与b奇偶性不同且c总是奇数

证明如下:

若a与b都是偶数,则c也是偶数,意味着a,b,c有公因数2,所以三元组不是本原的,其次,若a,b都是奇数,那么c必然是偶数,这样假设a=2x+1,b=2y+1,c=2z,代入技术分享,化简后得2x^2 + 2x + 2y^2 + 2y + 1 = 2z,显然不成立。所以,考虑到a,b的互换性,我们得出a是奇数,b是偶数,a,b,c没有公因数。

接着观察如下,如果(a,b,c)是本原勾股数组,则可进行因数分解:

a^2 = c^2 – b^2 = (c - b) * (c + b)

下面为举例:

3^2 = 5^2 - 4^2 = (5-4)(5+4) = 1 * 9,

15^2 = 17^2 - 8^2 = (17-8)(17+8) = 9 * 25,

21^2 = 29^2 - 20^2 = (29-20)(29+20) = 9 * 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,但是b和c没有公因数,所以d = 1或d = 2,但是d也整除(c - b)* (c + b) = a^2,因为a是奇数,所以只能是d = 1,所以c - b与c + b没有公因数。

现在我们知道c-b与c+b无公因数并且相乘为平方数,所以c-b与c+b自身都是平方数,记:

c + b = s^2, c – b = t^2, 其中s> t≥1是没有公因数的奇数。所以解为:

b = (s^2 - t^2)/ 2,

c = (s^2 + t^2)/ 2,

a = s * t.

从而得出勾股数组定理

每个本原勾股数组(a,b,c)(其中a为奇数,b为偶数)都可从如下公式得出:

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

其中a>t≥1是任意没有公因数的奇数。

如果取t=1,则三元组(s,  (s^2 - 1)/ 2, (s^2 + 1)/ 2),它的b与c值仅相差1.

 

今天正好做了一道有关的题:

题目链接:codeforces 707C. Pythagorean Triples

题意:给出一个数,构造勾股数。

题解:

a≤2时无解;

a为奇数时,直接用上面取t = 1的公式得b = (a^2 - 1)/ 2, c = (a^2 + 1)/ 2;

a为偶数时,当a = 4 *d时,直接可以套勾股数(3,4,5),从而b= 3 *d, c = 5 * d,

                     对于其他的偶数a,可以a = a/ 2, 将a化为奇数,再直接用上面公式即可.

 1 #include<cstdio> 2 int main(){ 3     long long a; 4     scanf("%I64d", &a); 5     if(a == 1 || a == 2) 6         printf("-1\n"); 7     else if(a % 4 == 0){ 8         printf("%I64d %I64d\n", a/4*3, a/4*5); 9     }10     else if(a % 2 == 0){11         a /= 2;12         printf("%I64d %I64d\n", (a*a-1)/2*2, (a*a+1)/2*2);13     }14     else15         printf("%I64d %I64d\n", (a*a-1)/2, (a*a+1)/2);16     return 0;17 }

 

勾股数组【学习笔记】