[CodeForces-707C] Pythagorean Triples【构造right三角形】

题意：

• 给出一个整形范围内的数n，判断是不是可以作为一个直角三角形的边，直角边斜边都可以. 另外，必须保证另外两条边是整数。

思路：

对于相邻平方差，我们可以得到{1, 3, 5, 7, ...}这样一个奇数数列。

1 = 1^2 - 0^2

3 = 2^2 - 1^2

5 = 3^2 - 2^2

……

由此可以得出，一个奇数n，有：

勾股定理大家一定知道！再接下来，我们考虑

（1）假设tmp = n^2，不是2的次幂. 那么tmp一直除以2，一定会得到一个奇数odd。

1. 由上所述，我们可以知道：对于最后这个奇数来说，我们一定可以得到平方差相减的也就是
2. 得到奇数的过程中，我们除以掉了一个2的次幂数，我们假设这个次幂是k。
3. 所以如果k是偶数，那么.  于是我们可以得到
4. 如果k是奇数，那么是不可以构成满足条件的三角形的

（2）假设tmp = n ^ 2是2的次幂

那由边长n构成的直角三角形一定是和345成比例的

（3）特殊考虑n为1和2的情况，是不能构成满足条件的三角形的

关于如何判断一个数是不是2的整数次幂 

• 我们知道2的整数次幂除了最高位为1，其余都为0. 所以假设n是2的整数次幂，那么n & (n - 1) == 0

 CODE

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;typedef long long ll;inline ll read()
{ll x = 0, f = 1; char c = getchar();while(c < '0' || c > '9') { if(c == '-') f = -f; c = getchar(); }while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }return x * f;
}const int maxN = 100005;ll n;int main()
{n = read();ll tmp = n * n;if(n == 1 || n == 2)cout << "-1\n";else if(! (n & (n - 1)))cout << n / 4 * 3 << " " << n / 4 * 5 << "\n";else{int mi = 0;while(!(tmp & 1)){tmp /= 2;mi ++;}if(mi & 1)cout << "-1\n";elsecout << (tmp / 2) * (1 << (mi / 2)) << ' ' << (tmp / 2 + 1) * (1 << (mi / 2)) << '\n';}return 0;
}