华为OD机试真题 - 勾股数元组 (D卷,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. 首先，我们需要找到给定范围内的所有勾股数元组。
2. 根据勾股定理，我们可以通过遍历a和b的值，计算c = sqrt(a^2 + b^2)，并判断c是否为整数。
3. 如果c是整数，则(a,b,c)是一个勾股数元组。
4. 接下来，我们需要判断这个勾股数元组是否满足两两互质的条件。
5. 我们可以通过计算a、b、c的最大公约数来判断它们是否互质。如果最大公约数为1，则它们是互质的。
6. 对于每个满足条件的勾股数元组，按照要求输出格式进行输出。
7. 如果给定范围内找不到满足条件的勾股数元组，则输出"NA"。

JavaScript算法源码

 
 const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 2) {
    const [n, m] = lines.map(Number);
    getResult(n, m);
    lines = [];
  }
});

function getResult(n, m) {
  const arr = Array.from({length: m - n + 1}, (_, i) => (i + n) ** 2);
  const set = new Set(arr);
  const res = [];

  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      const sum = arr[i] + arr[j];
      if (set.has(sum)) {
        res.push([Math.sqrt(arr[i]), Math.sqrt(arr[j]), Math.sqrt(sum)]);
      }
    }
  }

  const ans = res.filter((group) => {
    const [a, b, c] = group;
    return isRelativePrime(a, b) && isRelativePrime(a, c) && isRelativePrime(b, c);
  });

  if (!ans.length) return console.log("NA");

  ans.forEach((g) => console.log(g.join(" ")));
}

function isRelativePrime(x, y) {
  while (y > 0) {
    let mod = x % y;
    x = y;
    y = mod;
  }

  return x === 1;
}

Java算法源码

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import