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