C++에서 가능한 모든 하위 배열 중에서 최소 LCM 및 GCD 가능

크기가 N인 배열 arr이 있다고 가정합니다. N개의 양수가 있습니다. 가능한 모든 하위 배열의 최소 요소를 찾아야 합니다. 배열이 {2, 66, 14, 521}이고 최소 LCM이 2이고 GCD가 1이라고 가정합니다.

탐욕스러운 접근 방식을 사용하여 이 문제를 해결할 것입니다. 요소 수를 줄이면 LCM이 줄어들고 배열 크기를 늘리면 GCD가 작아집니다. 배열에서 가장 작은 요소를 찾아야 하며, 이는 단일 요소이며 LCM이 필요합니다. GCD의 경우 GCD는 배열의 모든 요소에 대한 GCD가 됩니다.

예시

#include <iostream>
#include <algorithm>
using namespace std;
int minimum_gcd(int arr[], int n) {
   int GCD = 0;
   for (int i = 0; i < n; i++)
   GCD = __gcd(GCD, arr[i]);
   return GCD;
}
int minimum_lcm(int arr[], int n) {
   int LCM = arr[0];
   for (int i = 1; i < n; i++)
   LCM = min(LCM, arr[i]);
   return LCM;
}
int main() {
   int arr[] = { 2, 66, 14, 521 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "LCM: " << minimum_lcm(arr, n) << ", GCD: " << minimum_gcd(arr, n);
}

출력

LCM: 2, GCD: 1