C++의 범위에서 비전이적 코프라임 삼중항 찾기

하한과 상한이 있고 쌍(x, y)이 동소(GCD는 1)이고 쌍(y, z)이 동이 되도록 비전이적 삼중항(x, 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;
   // 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