Pythagorean Triples [Codeforces 368 : Div2 C]

問題

http://codeforces.com/contest/707/problem/C

三辺が自然数の直角三角形の斜辺ではない辺の長さxがある。
この直角三角形の他の二辺を求めよ。

1 <= x <= 10^9

考察

1. 何か使えることが無いかとりあえずググる
2. https://ja.wikipedia.org/wiki/ピタゴラスの定理

1 <= n < mにおいて
a = m^2 - n^2
b = 2mn
c = m^2 + n^2
でa^2+b^2=c^2が成り立つ

3. これが使えそう
4. aは等式変形しておくと、a = (m + n)(m - n)となる
5. xが偶数であれば、n = 1, m = x / 2とすれば三平方が作れる
6. xが奇数であれば、m+n = x, m-n = 1として方程式を解く
7. 解くと、n = (x - 1) / 2, m = (x + 1) / 2 となるのでこれで答えればいい

実装

http://codeforces.com/contest/707/submission/20017232

typedef long long ll;
ll x;
pair<ll, ll> solve() {
	if(x <= 2) return make_pair(-1, -1);

	if (x % 2 == 0) {
		ll n = 1;
		ll m = x / 2;
		return make_pair(m*m - n*n, m*m + n*n);
	} else {
		ll n = (x - 1) / 2;
		ll m = (x + 1) / 2;
		return make_pair(2 * m*n, m*m + n*n);
	}
}
//-----------------------------------------------------------------
int main() {
	cin >> x;
	auto ans = solve();

	if (ans.first < 0)
		cout << -1 << endl;
	else
		cout << ans.first << " " << ans.second << endl;
}