Problem J29: Pythagorean Triples / 勾股数问题

版权信息： · 枚举与数论基础训练题

任务总览

题目描述

设有三个正整数 $a$、$b$、$c$ 满足以下条件：

$a ^ 2 + b ^ 2 = c ^ 2$那么我们称 $(a, b, c)$ 为一组​ 勾股数 ​（Pythagorean Triple）。

现在，给定一个正整数 $n$，请你找出所有满足 $c \leq n$ 的不同勾股数组合，并输出这些组数以及总数。

输入格式

一个正整数 $n$（$1 \leq n < 1000$），表示勾股数中最大允许的 $c$ 值。

输出格式

输出所有满足条件的勾股数组 $(a, b, c)$，​ 每组一行，按升序排列 ​（即 $a < b < c$），格式如下：

a, b, c

所有勾股数组输出完成后，再输出一行表示总共有多少组，格式如下：

共计有x组

输入输出样例

输入示例

20

输出示例

3, 4, 5
5, 12, 13
6, 8, 10
8, 15, 17
9, 12, 15
共计有5组

题目分析与解法

✅ 解法思路：

1. 使用三重嵌套或双重循环枚举 $a < b < c$；
2. 判断是否满足： $c≤n$ $a ^ 2 + b ^ 2 = c ^ 2 \quad \text{ 且 } \quad c \leq n3$.排除重复勾股数（如 $(6, 8, 10)$ 与 $(3, 4, 5)$ 的倍数组）可选；
3. 输出所有符合条件的 $(a, b, c)$ 并统计总数。

时间复杂度分析