刷题笔记合集🔗

勾股数元组

问题描述

如果3个正整数 满足 的关系，则称 为勾股数（著名的勾三股四弦五）。

为了探索勾股数的规律，我们定义如果勾股数 之间两两互质（即 与 ， 与 ， 与 之间均互质，没有公约数），则其为勾股数元组（例如 是勾股数元组， 则不是勾股数元组）。

请求出给定范围 内，所有的勾股数元组。

输入格式

起始范围 ，

结束范围 ，

输出格式

1. 请保证 ，输出格式： ；

2. 多组勾股数元组请按照 升序， 升序，最后 升序的方式排序输出；

3. 给定范围中如果找不到勾股数元组时，输出"NA"。

样例输入

1 20

5 10

样例输出

3 4 5
5 12 13
8 15 17

NA

数据范围

题解

这道题要求我们找出给定范围内的所有勾股数元组。解决这个问题分为两个主要步骤：

1. 找出给定范围内的所有勾股数
2. 筛选出其中两两互质的勾股数元组

对于第一步，我们需要找出满足 且 都在给定范围 内的所有三元组。最直接的方法是枚举范围内的所有可能的 和 值，然后计算 ，检查 是否为整数且落在范围内。

对于第二步，我们需要判断三个数是否两两互质。两个数互质意味着它们的最大公约数为1。我们可以使用辗转相除法（欧几里得算法）来计算最大公约数。

这道题的优化点在于如何高效地找出勾股数。一种方法是预先计算范围内所有数的平方值，存储在一个集合中，然后通过双重循环枚举 和 ，检查 是否在这个集合中，如果在，那么就找到了一组勾股数。

在时间复杂度方面，假设范围 的大小为 ：

• 预计算所有数的平方值需要 时间
• 枚举所有可能的 和 需要 时间
• 对于每组找到的勾股数，判断是否两两互质需要 时间

因此，总的时间复杂度大约为 。对于题目给定的范围（），这种方法是可以接受的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
n, m = map(int, input().split())

# 计算最大公约数的函数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# 判断两个数是否互质
def is_coprime(a, b):
    return gcd(a, b) == 1

# 找出给定范围内的所有勾股数元组
def find_pythagorean_triples():
    # 存储所有在范围内数的平方
    squares = {}
    for i in range(n, m + 1):
        squares[i * i] = i
    
    result = []
    
    # 枚举a和b
    for a in range(n, m + 1):
        for b in range(a + 1, m + 1):
            # 计算c^2
            c_squared = a * a + b * b
            
            # 检查c是否在范围内
            if c_squared in squares and squares[c_squared] <= m:
                c = squares[c_squared]
                
                # 检查a、b、c是否两两互质
                if (is_coprime(a, b) and is_coprime(a, c) and is_coprime(b, c)):
                    result.append((a, b, c))
    
    # 按要求排序
    result.sort()
    
    return result

# 主函数
triples = find_pythagorean_triples()

# 输出结果
if not triples:
    print("NA")
else:
    for triple in triples:
        print(*triple)

• Cpp

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

// 计算最大公约数的函数
int gcd(in