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

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