嘘~ 正在从服务器偷取页面 . . .

LOJ6568 「Project Euler 9」特殊勾股数题解

发布日期: 2022-10-21

更新日期: 2022-10-21

文章字数: 702

LOJ6568 「Project Euler 9」特殊勾股数题解

题意：

一组勾股数由三个自然数组成，\(a < b < c\) ，且 \[ a^2 + b^2 = c^2 \] 例如，\(3^2 + 4^2 = 9 + 16 = 25 = 5^2\)。

给出 \(N\)，请输出所有满足 \(a + b + c = N\) 的勾股数。

输入格式：

只有一行，一个整数 \(N\)。

输出格式：

多行，每行三个整数，\(a, b, c\) ，表示答案。

数据范围：

对于 \(100\%\) 的数据，\(N \leq 10^{12}\)。

~~想起上次做的圆上的整点，差点开始异想天开了~~

考虑一组 \(a,b,c\) 是勾股数的充要条件。

不妨设 \(a,b < c\) ，\(a,b\) 大小关系忽略，且 \(\gcd(a,b,c) = 1\) 。

则可以假设 \(a\) 为偶数，\(b,c\) 为奇数。

因为 \(a^2 + b^2 = c^2\) ，若 \(c\) 为偶数，则 \(a,b\) 均为偶数，与假设不符

若 \(c\) 为奇数，则 \(a,b\) 中至少有一个为偶数，由乘法的性质易得。

则此时一定存在正整数 \(u,v(u > v\) 且 \(u,v\) 奇偶性不同 \()\) 使得 \[ a = 2uv,~b = u^2 - v^2,~c = u^2 + v^2 \] 证明很简单，直接代入 \(a^2 + b^2 = c^2\) 即可。奇偶的话，很显然。

则对于一般的勾股数 \(a,b,c\) ，设 \(g = \gcd(a,b,c)\) ，则存在唯一表示 \[ a = 2uvd,~b=(u^2-v^2)d,~c=(u^2+v^2)d \] 则有 \(2du(u+v) = N\) 。

因此我们只需要枚举 \(\frac{N}{2}\) 的因数 \(d\) 和 \(u\) （显然 \(u\) 也是因数），从而计算出 \(v\) 。

则若 \(0<v<u \land \gcd(u,v) = 1 \land u,v\) 奇偶性不同

则 \(a = 2uvd,~b=(u^2-v^2)d,~c=(u^2+v^2)d\) 就是一组解，输出时注意 \(a,b\) 的大小关系

时间复杂度 \(\mathcal{O}(k^2)\) ，其中 \(k=d(N) \le 6720\) 。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define wr(a,b) cout << (a) << (b);
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int n;
int gcd(int a,int b) { return b==0 ? a : gcd(b,a%b); }
void solve(int n,int d)
{
    int a,b,u,v,l = floor(sqrt(n * 0.5));
    if(n < 12 || n & 1) return;
    for(a = ceil(sqrt(n * 0.25)); a <= l; a++)
        if(n % (a * 2) == 0)
        {
            b = n / (a * 2) - a;
            if(gcd(a,b) == 1 && (a ^ b) & 1)
            {
                tie(u,v) = minmax(a*a - b*b, 2*a*b);
                wr(u * d, ' ');wr(v * d, ' ');wr((a * a + b * b) * d, '\n');
            }
        }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int k=1; k * k <= n; k++)
        if(n % k == 0) { solve(n/k, k); k * k != n && (solve(k,n/k),0); }
    return 0;
}