Giả sử chúng ta có một mảng arr kích thước N. nó có N số dương. Chúng ta phải tìm các phần tử tối thiểu của tất cả các mảng con có thể có. Giả sử mảng là {2, 66, 14, 521}, thì LCM tối thiểu là 2 và GCD là 1.
Chúng tôi sẽ giải quyết vấn đề này bằng cách sử dụng một cách tiếp cận tham lam. Nếu chúng ta giảm số phần tử, thì LCM sẽ ít hơn, và nếu chúng ta tăng kích thước mảng, GCD sẽ ít hơn. Chúng ta cần tìm phần tử nhỏ nhất từ mảng, là một phần tử đơn lẻ, phần tử này sẽ được yêu cầu LCM. Đối với GCD, GCD sẽ là GCD của tất cả các phần tử của mảng.
Ví dụ
#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);
} Đầu ra
LCM: 2, GCD: 1