codeforces #368 div 2 C. Pythagorean Triples (构造,数学)

题目链接

题意:给出一个数,问包含这个数三个数组成的勾股数,输出另外两个数。

思路:

所谓勾股数,就是当组成一个直角三角形的三边长都为正整数时,我们就称这一组数为勾股数.
那么,组成一组勾股数的三个正整数之间,是否具有一定的规律可寻呢?下面我们一起来观察几组勾股数:
规律一:在勾股数(3,4,5)、(5,12,13)、(7,24,25)(9,40,41)中,我们发现
由(3,4,5)有:32=9=4+5
由(5,12,13)有:52=25=12+13
由(7,24,25)有:72=49=24+25
由(9,40,41)有:92=81=40+41.
即在一组勾股数中,当最小边为奇数时,它的平方刚好等于另外两个连续的正整数之和.因此,我们把它推广到一般,从而可得出以下公式:
∵(2n+1)²=4n²+4n+1=(2n²+2n)+(2n²+2n+1)
∴(2n+1)²+(2n²+2n)²=(2n²+2n+1)²(n为正整数)
证明(略)
勾股数公式一:(2n+1,2n²+2n,2n²+2n+1)(n为正整数)
规律二:在勾股数(6,8,10)、(8,15,17)、(10,24,26)中,我们发现
由(6,8,10)有:62=36+2×(8+10)
由(8,15,17)有:82=64=2×(15+17)
由(10,24,26)有:102=100=2×(24+26)
即在一组勾股数中,当最小边为偶数时,它的平方刚好等于两个连续整数之和的二倍,推广到一般,从而可得出另一公式:
∵(2n)2=4n2=2[(n2-1)+(n2+1)]
∴(2n)2+(n2-1)2=(n2+1)2(n≥2且n为正整数)
证明(略)
勾股数公式二:(2n,n²-1,n²+1)(n≥2且n为正整数)
利用以上两个公式,我们可以快速写出各组勾股数.

结论是:  n<=2无解。

n为奇数用公式1构造。

n为偶数用公式2构造。

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz