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