勾股数元组

真题目录: 点击去查看

E 卷 100分题型

题目描述

如果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

输出描述

1. a,b,c请保证a < b < c,输出格式：a b c；
2. 多组勾股数元组请按照a升序，b升序，最后c升序的方式排序输出；
3. 给定范围中如果找不到勾股数元组时，输出”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“

题解

思路：

1. 枚举[n,m-1]范围内所有可能的a、b,通过a ^ 2 + b ^ 2可以得出 c ^2的值, √c^2判断是否大于m,并且为整数
2. 使用辗转相除法判断 a b c是否相互互质

c++

#include <cmath>
#include<iostream>
#include<vector>
#include<string>
#include <utility> 
#include <sstream>
#include<algorithm>
#include<math.h>
#include<set>
using namespace std;// 辗转相除法判断是否互质
bool isCoprime(int a, int b) {while (b != 0) {int tmp = b;b = a % b;a = tmp;}return a == 1;
}// 判断是否相互互质
bool areCoprime(int a, int b, int c) {return isCoprime(a, b) && isCoprime(a, c)&& isCoprime(b, c);
}int main() {int n, m;cin >> n >> m;vector<string> ans;vector<long> num(m-n+1, 0);// 计算范围内每个值的平方值for (int i = n ; i <= m ; i++) {num[i-n] = (long)i * i;}// 用于c是否在指定范围内set<long> s(num.begin(), num.end());for (int i = 0; i < num.size(); i++) {for (int j = i + 1; j < num.size(); j++) {long aSquared = num[i];long bSquared = num[j];long cSquaredc= aSquared + bSquared;// c超出范围或者为小数if (s.find(cSquaredc) == s.end()) {continue;}int c = (int)sqrt(cSquaredc);// 判断是否互质if (areCoprime(i+n, j+n, c)) {ans.push_back(std::to_string(i + n) +" " +std::to_string(j+n) + " " +std::to_string(c));} }} if (ans.size() == 0) {cout << "NA";return 0;} for (int i = 0; i < ans.size(); i++) {cout << ans[i] << endl;}return 0;
}

JAVA

import java.util.*;public class Main {// 辗转相除法判断是否互质private static boolean isCoprime(int a, int b) {while (b != 0) {int tmp = b;b = a % b;a = tmp;}return a == 1;}// 判断是否相互互质private static boolean areCoprime(int a, int b, int c) {return isCoprime(a, b) && isCoprime(a, c) && isCoprime(b, c);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取输入int n = scanner.nextInt();int m = scanner.nextInt();List<String> ans = new ArrayList<>();for (int a = n; a < m; a++) {for (int b = a + 1; b < m; b++) {long cSquared = (long) a * a + (long) b * b;// 计算 a^2 + b^2 的根号值，转换为 int 是向下取整int c = (int) Math.sqrt(cSquared);// 判断是否符合条件if ((long) c * c == cSquared && c <= m && areCoprime(a, b, c)) {ans.add(a + " " + b + " " + c);}}}if (ans.isEmpty()) {System.out.println("NA");} else {for (String triplet : ans) {System.out.println(triplet);}}scanner.close();}
}

Python

import math# 辗转相除法判断是否互质
def is_coprime(a, b):while b != 0:a, b = b, a % breturn a == 1# 判断是否相互互质
def are_coprime(a, b, c):return is_coprime(a, b) and is_coprime(a, c) and is_coprime(b, c)def main():n = int(input())m = int(input())ans = []num = [0] * (m - n + 1)# 计算 n 到 m 之间每个数的平方for i in range(n, m + 1):num[i - n] = i * is = set(num)  # 用集合去重# 寻找勾股数三元组for i in range(len(num)):for j in range(i + 1, len(num)):a_squared = num[i]b_squared = num[j]c_squared = a_squared + b_squared// 判断c^2是否是 [n,m]中整数的平方if c_squared not in s:continuec = int(math.sqrt(c_squared))// 判断是否互质if are_coprime(i + n, j + n, c):ans.append(f"{i + n} {j + n} {c}")# 输出结果if not ans:print("NA")else:for result in ans:print(result)if __name__ == "__main__":main()

JavaScript

const readline = require("readline");// 辗转相除法判断是否互质
function isCoprime(a, b) {while (b !== 0) {let tmp = b;b = a % b;a = tmp;}return a === 1;
}// 判断是否相互互质
function areCoprime(a, b, c) {return isCoprime(a, b) && isCoprime(a, c) && isCoprime(b, c);
}// 创建读取接口
const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});// 获取用户输入
let n, m;
rl.question("", (input) => {n = parseInt(input);rl.question("", (input) => {m = parseInt(input);let ans = [];let num = [];// 计算范围内每个值的平方值for (let i = n; i <= m; i++) {num.push(i * i);}// 用于c是否在指定范围内let s = new Set(num);// 遍历 num 数组，检查符合条件的勾股数三元组for (let i = 0; i < num.length; i++) {for (let j = i + 1; j < num.length; j++) {let aSquared = num[i];let bSquared = num[j];let cSquared = aSquared + bSquared;// c超出范围或者为小数if (!s.has(cSquared)) {continue;}let c = Math.sqrt(cSquared);// 判断是否互质if (Number.isInteger(c) && areCoprime(i + n, j + n, c)) {ans.push(i + n + " " + (j + n) + " " + c);}}}// 输出结果if (ans.length === 0) {console.log("NA");} else {ans.forEach((item) => console.log(item));}rl.close();});
});

Go

package mainimport ("fmt""math"
)// 辗转相除法判断是否互质
func isCoprime(a, b int) bool {for b != 0 {tmp := bb = a % ba = tmp}return a == 1
}// 判断是否相互互质
func areCoprime(a, b, c int) bool {return isCoprime(a, b) && isCoprime(a, c) && isCoprime(b, c)
}func main() {var n, m int// 输入n和mfmt.Scanf("%d", &n)fmt.Scanf("%d", &m)var ans []stringvar num []int// 计算范围内每个值的平方值for i := n; i <= m; i++ {num = append(num, i*i)}// 用于c是否在指定范围内s := make(map[int]struct{})for _, v := range num {s[v] = struct{}{}}// 遍历num数组，检查符合条件的勾股数三元组for i := 0; i < len(num); i++ {for j := i + 1; j < len(num); j++ {aSquared := num[i]bSquared := num[j]cSquared := aSquared + bSquared// c超出范围或者为小数if _, found := s[cSquared]; !found {continue}c := int(math.Sqrt(float64(cSquared)))// 判断是否互质if math.Sqrt(float64(cSquared)) == float64(c) && areCoprime(i+n, j+n, c) {ans = append(ans, fmt.Sprintf("%d %d %d", i+n, j+n, c))}}}// 输出结果if len(ans) == 0 {fmt.Println("NA")} else {for _, result := range ans {fmt.Println(result)}}
}