Codeforces 707C Pythagorean Triples(构造三条边都为整数的直角三角形)

题目链接:http://codeforces.com/contest/707/problem/C

题目大意:给你一条边,问你能否构造一个包含这条边的直角三角形且该直角三角形三条边都为整数,能则输出另外两条边,否则输出-1“”。

解题思路:下面是我从作业帮上找的- -,

利用平方差公式
令斜边为c,直角边为a、b,且b为最短边
c²-a²=(c+a)(c-a)
因此(c+a)(c-a)是完全平方数,且(c-a)是(c+a)的一个因数
1、如果(c-a)=1,则(c+a)是完全平方数(最短边是任意大于2的奇数)
例如:5、4、3;13、12、5;25、24、7;41、40、9;...
2、如果(c-a)=2,则(c+a)/2是完全平方数(最短边是任意大于2的偶数)
例如:5、3、4;10、8、6;17、15、8;26、24、10;...
即:最短边是任意一个大于2的正整数,都可以配成一个三边都是整数的直角三角形.

当直角边b已知,b<=2时无解,接下来分两种情况考虑:①b为奇数,因c-a=1得c=a+1,所以(c-a)*(c+a)=2*a+1=b*b,可得a=(b*b-1)/2.

                         ②b为偶数,因c-a=2得c=a+2,所以(c-a)*(c+a)=4*(a+1)=b*b,可得a=b*b/4-1.

代码:

 #include<iostream>
using namespace std;
const int N=1e9+;
typedef long long LL; int main(){
LL b;
cin>>b;
if(b>){
LL a;
if(b%){
a=(b*b-)/;
cout<<a<<" "<<a+<<endl;
}
else{
a=b*b/-;
cout<<a<<" "<<a+<<endl;
}
}
else
puts("-1");
return ;
}
上一篇:Codeforces - 1202D - Print a 1337-string... - 构造


下一篇:(netty宝贵知识)