勾股数元组
标题：勾股数元组 | 时间限制：1秒 | 内存限制：262144K | 语言限制：不限
如果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]内，所有的勾股数元祖。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool ispain(int a, int b) {
if (a == 1 || b == 1) {
return 1;
}
while (1) {
int t = a % b;
if (t == 0) {
break;
} else {
a = b;
b = t;
}
}
if (b > 1) {
return 0;
}
return 1;
}
int main() {
int n, m;
cin>>n>>m;
vector<vector<int>> ans;
for (int i = n; i <= m - 2; i++) {
for (int k = m; k > i + 1; --k) {
if (!ispain(i, k)) {
continue;
}
int t = (k - i) * (k + i);
for (int j = k - 1; j > i; --j) {
if (ispain(i, k) && ispain(j, k) && t == j * j) {
ans.push_back({i, j, k});
}
}
}
}
if (ans.empty()) {
cout<<"NA"<<endl;
}
sort(ans.begin(), ans.end(), [] (auto &a, auto &b) {
if (a[0] > b[0]) {
return 0;
} else if (a[0] == b[0]) {
if (a[1] > b[1]) {
return 0;
} else if (a[1] == b[1]) {
if (a[2] > b[2]) {
return 0;
}
}
}
return 1;});
for (auto & s : ans) {
cout<<s[0]<<" "<<s[1]<<" "<<s[2]<<endl;
}
return 0;
}
import math
start = int(input())
end = int(input())
LEN = math.ceil(math.sqrt(end))
ans = []
for i in range(1, LEN):
for j in range(i + 1, LEN):
# check gcd
if math.gcd(i, j) != 1:
continue
a = j ** 2 - i ** 2
b = 2 * i * j
if a < start or b < start:
continue
c = i ** 2 + j ** 2
if c <= end:
if math.gcd(a, b) == 1 and math.gcd(a, c) == 1 and \
math.gcd(b, c) == 1:
t = [a, b, c]
t.sort()
ans.append(t)
if len(ans) > 0:
ans.sort()
for t in ans:
print(f"{t[0]} {t[1]} {t[2]}")
else:
print("NA")
//manfen
投递贝壳找房等公司10个岗位 >
