問題
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; }