Pythagorean Triples 题解

ryl_ahu · 2023-07-23 16:57:23 · 题解

首先我们要知道勾股定理：a ^ 2 + b ^ 2 = c ^ 2。

然后我们设一个数 n = a ^ 2。

这样 n = c ^ 2 - b ^ 2。

根据平方差公式，所以 n = (c + b) \times (c - b)。

我们可以使 c + b = n 并且 c - b = 1 这样 1 \times n = n 就可以了。

随后我们解出这个方程，便可得知：

所以，如果 n 是奇数，那么 c 和 b 就出来了：

if (a % 2 == 1) {
    a *= a;
    cout << (a - 1) / 2 << " ";
    cout << (a + 1) / 2 << endl;
}

接下来，我们再来判断 n 是偶数的情况：如果 n 是偶数，我们就将 n 一直除以 2，直到 n 除以 2 余 1。用奇数的算法算出 b 和 c，再乘以刚才除的那些 2 就可以啦：

if (a % 2 == 0) {
    int ans = 1;
    while (a % 2 == 0) {
        a /= 2;
        ans *= 2;
    }
}

还有，如果 n 一直除以 2 除的最后正剩下 1，那就得特殊判断：用 3、4、5 这一组勾股数带进去就可以了：

if (a == 1)
{
    cout << 3 * ans / 4 << " ";
    cout << 5 * ans / 4 << endl;
}

对了！我们还要判断一下 a 是否小于 3，因为没有小于 3 的勾股数，特判即可。

结尾附上总代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long a;
    cin >> a;
    if (a <= 2) {
        cout << -1 << endl;
        return 0;
    }
    if (a % 2 == 1) {
        a *= a;
        cout << (a - 1) / 2 << " ";
        cout << (a + 1) / 2 << endl;
    }
    if (a % 2 == 0) {
        int ans = 1;
        while (a % 2 == 0) {
            a /= 2;
            ans *= 2;
        }
        if (a == 1)
        {
            cout << 3 * ans / 4 << " ";
            cout << 5 * ans / 4 << endl;
            return 0;
        }
        a *= a;
        cout << (a - 1) * ans / 2 << " ";
        cout << (a + 1) * ans / 2 << endl;
    }
    return 0;
}