สมมติว่าเรามีขอบเขตล่างและบน และเราต้องหาแฝดสามที่ไม่เปลี่ยนรูป (x, y, z) โดยที่คู่ (x, y) เป็น coprime (GCD คือ 1) คู่ (y, z) เป็น coprime แต่คู่ (x, z) ไม่ใช่คู่ coprime ตัวอย่างเช่น หากขอบล่างคือ 2 และขอบบนคือ 10 ดังนั้นองค์ประกอบคือ {2, 3, 4, 5, 6, 7, 8, 9, 10} แฝดสามที่เป็นไปได้คือ (4, 7, 8 ) ในที่นี้ (4, 7) และ (7, 8) คือ coprime แต่ (4, 8) ไม่ใช่คู่ของ coprime
เราจะปฏิบัติตามแนวทางที่ไร้เดียงสาเพื่อแก้ปัญหานี้ เราจะสร้างแฝดสามที่เป็นไปได้ทั้งหมดในช่วงขอบเขตล่างและขอบเขตบน จากนั้นให้ตรงกับเกณฑ์
ตัวอย่าง
#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;
// Generate and check for all possible triplets
// between L and 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
