如果三个正整数A、B、C ，A² + B² = C² 则为勾股数，
如果ABC之间两两互质，即A与B，A与C，B与C均互质没有公约数，则称其为勾股数元组。
请求出给定 n ~ m 范围内所有的勾股数元组。
起始范围
1 < n < 10000
n < m < 10000
ABC保证A < B < C
输出格式A B C
多组勾股数元组，按照A B C升序的排序方式输出。
若给定范围内，找不到勾股数元组时，输出Na。
1
20
3 4 5
5 12 13
8 15 17
5
10
Na
本题是一道求解勾股数元组的问题。勾股数的定义是三个正整数 、、，满足 ，其中 、、 两两互质，则称其为勾股数元组。
求解思路是枚举 和 ，然后再计算出 ，判断是否满足勾股数条件和两两互质条件。需要注意的是， 和 的范围是 到 ， 的范围是 ，因为 和 不能大于 。
对于每个 ，需要枚举 ，范围是 到 。对于每组 和 ，需要计算 ，因此计算 的次数也与 有关，最大不超过 。因此，时间复杂度为 。
空间复杂度为 ，只需要几个变量存储数据即可。
参考代码中，使用了一个求最大公约数的函数 gcd，其时间复杂度为 。因此，总时间复杂度为 。
#include <stdio.h>
#include <math.h>
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
int n, m;
while (scanf("%d%d", &n, &m) == 2) {
int found = 0;
for (int i = n; i <= m; i++) {
for (int j = i + 1; j <= m; j++) {
int k = (int) sqrt(i * i + j * j);
if (k > m) {
break;
}
if (k * k == i * i + j * j) {
if (gcd(i, j) == 1 && gcd(j, k) == 1) {
printf("%d %d %d\\n", i, j, k);
found = 1;
}
}
}
}
if (!found) {
printf("Na\\n");
}
}
return 0;
}
#include <iostream>
#include <cmath>
using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
int n, m;
while (cin >> n >> m) {
int found = 0;
for (int i = n; i <= m; i++) {
for (int j = i + 1; j <= m; j++) {
int k = (int) sqrt(i * i + j * j);
if (k > m) {
break;
}
if (k * k == i * i + j * j) {
if (gcd(i, j) == 1 && gcd(j, k) == 1) {
cout << i << " " << j << " " << k << endl;
found = 1;
}
}
}
}
if (!found) {
cout << "Na" << endl;
}
}
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int n = in.nextInt();
int m = in.nextInt();
boolean found = false;
for (int i = n; i <= m; i++) {
for (int j = i + 1; j <= m; j++) {
int k = (int) Math.sqrt(i * i + j * j);
if (k > m) {
break;
}
if (k * k == i * i + j * j) {
if (gcd(i, j) == 1 && gcd(j, k) == 1) {
System.out.printf("%d %d %d\\n", i, j, k);
found = true;
}
}
}
}
if (!found) {
System.out.println("Na");
}
}
}
private static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
function gcd(a, b) {
return b == 0 ? a : gcd(b, a % b);
}
rl.on('line', line => {
const [n, m] = line.split(' ').map(Number);
let found = false;
for (let i = n; i <= m; i++) {
for (let j = i + 1; j <= m; j++) {
const k = Math.sqrt(i * i + j * j);
if (k > m) {
break;
}
if (k * k == i * i + j * j) {
if (gcd(i, j) == 1 && gcd(j, k) == 1) {
console.log(`${i} ${j} ${k}`);
found = true;
}
}
}
}
if (!found) {
console.log('Na');
}
});
package main
import (
"fmt"
"math"
)
func gcd(a, b int) int {
if b == 0 {
return a
} else {
return gcd(b, a%b)
}
}
func main() {
var n, m int
for {
_, err := fmt.Scan(&n, &m)
if err != nil {
break
}
found := false
for i := n; i <= m; i++ {
for j := i + 1; j <= m; j++ {
k := int(math.Sqrt(float64(i*i + j*j)))
if k > m {
break
}
if k*k == i*i+j*j {
if gcd(i, j) == 1 && gcd(j, k) == 1 {
fmt.Printf("%d %d %d\\n", i, j, k)
found = true
}
}
}
}
if !found {
fmt.Println("Na")
}
}
}