题面描述

给定两个正整数 $N$ 和 $M$，其中 $1 \leq N \leq 10000$ 且 $N < M \leq 10000$，要求在区间 $[N, M]$ 内找出所有的勾股数元组 $(a, b, c)$，满足以下条件：

1. $a < b < c$ 且 $a^2 + b^2 = c^2$；
2. $(a, b, c)$ 两两互质，即 $a$ 与 $b$，$a$ 与 $c$，$b$ 与 $c$ 之间均无公约数；
3. 输出的勾股数元组按照 $a$ 升序，$b$ 升序，$c$ 升序排列；
4. 如果在给定范围内找不到满足条件的勾股数元组，输出 “NA”。

思路

1. 生成勾股数元组：

   • 使用欧几里得公式生成所有原始勾股数元组 $(a, b, c)$。欧几里得公式指出，对于任意一对正整数 $m$ 和 $n$，其中 $m > n$，$m$ 和 $n$ 互质且其中一个为奇数，原始勾股数元组可以表示为：$$a = m^2 - n^2, \quad b = 2mn, \quad c = m^2 + n^2$$
   • 由于原始勾股数元组已经满足两两互质的条件，因此无需进一步检查。

2. 限制范围：

   • 生成的 $a$, $b$, $c$ 必须满足 $N \leq a < b < c \leq M$。
   • 遍历可能的 $m$ 和 $n$，生成所有满足条件的 $(a, b, c)$。

3. 排序输出：

   • 将所有符合条件的勾股数元组存储在一个容器中。
   • 按照 $a$ 升序，若 $a$ 相同则按 $b$ 升序，若 $b$ 也相同则按 $c$ 升序排序。

4. 处理无解情况：

   • 如果在给定范围内没有找到任何满足条件的勾股数元组，则输出 “NA”。

cpp

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

// 结构体表示勾股数元组
struct PythagoreanTriple {
    int a;
    int b;
    int c;
};

// 主函数
int main(){
    int N, M;
    // 读取输入
    cin >> N >> M;
    
    vector<PythagoreanTriple> triples;
    
    // 遍历m和n生成原始勾股数元组
    for(int m = 2; m*m <= M; m++){
        for(int n = 1; n < m; n++){
            // m和n必须互质且一个奇一个偶
            if( (m - n) % 2 == 1 && gcd(m, n) == 1 ){
                int a = m*m - n*n;
                int b = 2*m*n;
                int c = m*m + n*n;
                
                // 确保a < b
                if(a > b) swap(a, b);
                
                // 检查是否在范围内
                if(a >= N && b >= N && c >= N && a <= M && b <= M && c <= M){
                    triples.push_back(PythagoreanTriple{a, b, c});
                }
            }
        }
    }
    
    // 排序按照a, then b, then c
    sort(triples.begin(), triples.end(), [&](const PythagoreanTriple &x, const PythagoreanTriple &y) -> bool{
        if(x.a != y.a) return x.a < y.a;
        if(x.b != y.b) return x.b < y.b;
        return x.c < y.c;
    });
    
    // 输出结果
    if(triples.empty()){
        cout << "NA" << endl;
    }
    else{
        for(auto &triple : triples){
            cout << triple.a << " " << triple.b << " " << triple.c << "\n";
        }
    }
    
    return 0;
}

java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

// 结构体表示勾股数元组
class PythagoreanTriple {
    int a;
    int b;
    int c;

    PythagoreanTriple(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();

        List<PythagoreanTriple> triples = new ArrayList<>();

        // 遍历m和n生成原始勾股数元组
        for (int m = 2; m * m <= M; m++) {
            for (int n = 1; n < m; n++) {
                // m和n必须互质且一个奇一个偶
                if ((m - n) % 2 == 1 && gcd(m, n) == 1) {
                    int a = m * m - n * n;
                    int b = 2 * m * n;
                    int c = m * m + n * n;

                    // 确保a < b
                    if (a > b) {
                        int temp = a;
                        a = b;
                        b = temp;
                    }

                    // 检查是否在范围内
                    if (a >= N && b >= N && c >= N && a <= M && b <= M && c <= M) {
                        triples.add(new PythagoreanTriple(a, b, c));
                    }
                }
            }
        }

        // 排序按照a, then b, then c
        Collections.sort(triples, new Comparator<PythagoreanTriple>() {
            @Override
            public int compare(PythagoreanTriple x, PythagoreanTriple y) {
                if (x.a != y.a) return Integer.compare(x.a, y.a);
                if (x.b != y.b) return Integer.compare(x.b, y.b);
                return Integer.compare(x.c, y.c);
            }
        });

        // 输出结果
        if (triples.isEmpty()) {
            System.out.println("NA");
        } else {
            for (PythagoreanTriple triple : triples) {
                System.out.println(triple.a + " " + triple.b + " " + triple.c);
            }
        }
    }

    // 计算最大公约数
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

python

import math

# 定义一个元组表示勾股数元组
class PythagoreanTriple:
    def __init__(self, a, b, c):
        self.a = a
        self.b = b
        self.c = c

# 主函数
def main():
    import sys
    # 读取输入
    input = sys.stdin.read().split()
    N = int(input[0])
    M = int(input[1])
    
    triples = []
    
    # 遍历m和n生成原始勾股数元组
    m = 2
    while m*m <= M:
        for n in range(1, m):
            # m和n必须互质且一个奇一个偶
            if (m - n) % 2 == 1 and math.gcd(m, n) == 1:
                a = m*m - n*n
                b = 2*m*n
                c = m*m + n*n
                # 确保a < b
                if a > b:
                    a, b = b, a
                # 检查是否在范围内
                if N <= a <= M and N <= b <= M and N <= c <= M:
                    triples.append(PythagoreanTriple(a, b, c))
        m +=1
    
    # 排序按照a, then b, then c
    triples.sort(key=lambda x: (x.a, x.b, x.c))
    
    # 输出结果
    if not triples:
        print("NA")
    else:
        for triple in triples:
            print(f"{triple.a} {triple.b} {triple.c}")

# 调用主函数
if __name__ == "__main__":
    main()

题目描述

如果 $3$ 个正整数($a,b,c$)满足 $a^2 + b^2 = c^2$ 的关系，则称($a,b,c$)为勾股数（著名的勾三股四弦五），

为了探索勾股数的规律，我们定义如果勾股数($a,b,c$)之间两两互质（即 $a$ 与 $b，a$ 与 $c，b$ 与 $c$ 之间均互质，没有公约数），则其为勾股数元组（例如($3,4,5$)是勾股数元组，($6,8,10$)则不是勾股数元组）。

请求出给定范围 $[N,M]$ 内，所有的勾股数元组。

输入描述

起始范围 $N$ ，$1 <= N <= 10000$

结束范围 $M，N < M <= 10000$

输出描述

$a,b,c$ 请保证 $a < b < c$,输出格式：$a$ $b$ $c$；

多组勾股数元组请按照 $a$ 升序，$b$ 升序，最后 $c$ 升序的方式排序输出；

给定范围中如果找不到勾股数元组时，输出”$NA$“。

样例1

输入

1
20

输出

3 4 5
5 12 13
8 15 17

说明

$[1,20]$ 范围内勾股数有：($3$ $4$ $5$)，($5$ $12$ $13$)，($6$ $8$ $10$)，($8$ $15$ $17$)，($9$ $12$ $15$)，($12$ $16$ $20$)；

其中，满足($a,b,c$)之间两两互质的勾股数元组有：($3$ $4$ $5$)，($5$ $12$ $13$)，($8$ $15$ $17$);

按输出描述中顺序要求输出结果。

样例2

输入

5
10

输出

`` NA

**说明**

$[5,10]$ 范围内勾股数有：($6$ $8$ $10$)；

其中，没有满足($a,b,c$)之间两两互质的勾股数元组；

给定范围中找不到勾股数元组，输出”$NA$“