在C ++中找到某个范围内的非传递性互质三元组
假设我们有下限和上限，并且我们必须找到非传递性三元组(x,y,z)，使得对(x,y)是互质的（GCD为1），对(y,z)是互质的，但对(x,z)不是互质对。例如，如果下限是2，上限是10，则元素是{2，3，4，5，6，7，8，9，10}，这里可能的三元组是（4，7，8），此处(4,7)和(7,8)是互质的，但(4,8)不是互质的。
我们将采用幼稚的方法来解决此问题。我们将生成下限和上限范围内的所有可能的三元组，然后匹配条件。
示例
#include <iostream>
#include <algorithm>
using namespace std;
bool isCoprime(int a, int b){
return (__gcd(a, b) == 1);
}
void tripletInRange(int left, int right) {
bool flag = false;
int A, B, C;
//生成并检查所有可能的三元组
//在L和R之间
for (int a = left; a <= right; a++) {
for (int b = a + 1; b <= right; b++) {
for (int c = b + 1; c <= right; c++) {
if (isCoprime(a, b) && isCoprime(b, c) && ! isCoprime(a, c)) {
flag = true;
A = a;
B = b;
C = c;
break;
}
}
}
}
if (flag == true) {
cout << "(" << A << ", " << B << ", " << C << ")" << " is one
such possible triplet between " << left << " and " << right << endl;
} else {
cout << "No Such Triplet exists between " << left << " and " << right << endl;
}
}
int main() {
int left = 2, right = 10;
tripletInRange(left, right);
}输出结果
(8, 9, 10) is one such possible triplet between 2 and 10