文章目录
一、题目🎃题目描述🎃输入输出🎃样例1🎃样例2 二、思路参考三、代码参考 作者：KJ.JK🍂个人博客首页：KJ.JK
🍂专栏介绍：华为OD机试真题汇总，定期更新华为OD各个时间阶段的机试真题，每日定时更新，本专栏将使用C语言进行更新解答，包含真题，思路分析，代码参考，欢迎大家订阅学习
一、题目
🎃题目描述
如果3个正整数(a,b,c)满足a2 + b2 = c2的关系，则称(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
输出
1、a,b,c请保证a < b < c,输出格式：a b c；
2、多组勾股数元组请按照a升序，b升序，最后c升序的方式排序输出；
3、给定范围中如果找不到勾股数元组时，输出”NA“。
🎃样例1
输入120输出3 4 55 12 138 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
输入510输出NA说明：[5, 10]范围内勾股数有：(6 8 10)；其中，没有满足(a,b,c)之间两两互质的勾股数元组；给定范围中找不到勾股数元祖，输出”NA“
二、思路参考
1、首先，我们需要编写一个函数来判断两个数是否互质。互质的条件是它们的最大公约数为 1。我们可以使用辗转相除法来求两个数的最大公约数。如果最大公约数为 1，则两个数互质。
2、接下来，我们可以使用两重循环遍历范围 [N, M] 内的所有数对 (a, b)，其中 N <= a < b <= M。对于每个数对，我们计算 c 的值，并判断是否满足勾股数条件和两两互质条件。
3、勾股数条件是 a^2 + b^2 = c^2。我们计算 c 的平方，然后取其平方根，将结果转换为整数。如果平方根的整数部分的平方等于 c 的平方，则满足勾股数条件。
4、在判断勾股数条件的基础上，我们还需要判断 (a, b, c) 是否两两互质。即判断 a 和 b、a 和 c、b 和 c 是否互质。我们可以调用之前编写的判断互质的函数进行判断。
5、如果满足勾股数条件和两两互质条件，将勾股数元组 (a, b, c) 添加到结果集合中。
6、最后，我们对结果集合进行排序，按照 a 升序、b 升序、最后 c 升序的方式排序。
根据题目要求的输出格式，按照每个勾股数元组一行的形式输出结果。
如果在给定范围内找不到勾股数元组，则输出 “NA”。
三、代码参考
#include <stdio.h>#include <stdbool.h>#include <math.h>// 判断两个数是否互质bool areCoprime(int a, int b) {int temp;while (b != 0) {temp = b;b = a % b;a = temp;}return a == 1;}int main() {int N, M;scanf("%d %d", &N, &M);bool found = false; // 标记是否找到勾股数元组for (int a = N; a < M; a++) {for (int b = a + 1; b < M; b++) {int c_square = a * a + b * b;int c = (int)sqrt(c_square);if (c * c == c_square && areCoprime(a, b) && areCoprime(a, c) && areCoprime(b, c)) {printf("%d %d %d\n", a, b, c);found = true;}}}if (!found) {printf("NA\n");}return 0;}
