BCNN và UCLN nhỏ nhất trong tất cả các mảng con có thể trong C++

Cho mảng arr kích thước N gồm các số dương. Tìm BCNN và UCLN nhỏ nhất trong tất cả các mảng con có thể. Ví dụ mảng {2, 66, 14, 521}, BCNN nhỏ nhất là 2, UCLN nhỏ nhất là 1.

Giải bằng tham lam: Giảm số phần tử thì BCNN giảm, tăng kích thước mảng thì UCLN giảm. BCNN nhỏ nhất là phần tử nhỏ nhất của mảng (mảng con 1 phần tử). UCLN nhỏ nhất là UCLN của toàn bộ mảng.

Ví dụ minh họa

#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 << "BCNN: " << minimum_lcm(arr, n) << ", UCLN: " << minimum_gcd(arr, n);
    return 0;
}

Kết quả

BCNN: 2, UCLN: 1