Bội chung nhỏ nhất

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Hàm tính UCLN (gcd) của 2 số
int gcd(int a, int b) {
    while (b != 0) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

// Hàm tính BCNN (lcm) của 2 số
int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;
}

int main() {
    const int MOD = 10007;
    int T;
    cin >> T;

    vector<int> results(T); // Dùng để lưu kết quả của tất cả các test case

    for (int t = 0; t < T; t++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        // Khởi tạo biến để lưu tổng BCNN của các tập con
        int totalLCM = 0;

        // Duyệt qua tất cả các tập con
        // Sử dụng bitmask để xét tất cả các tập con
        for (int mask = 1; mask < (1 << n); mask++) {
            int currentLCM = 1;
            bool first = true;

            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    if (first) {
                        currentLCM = a[i];
                        first = false;
                    } else {
                        currentLCM = lcm(currentLCM, a[i]);
                    }
                }
            }

            // Cộng BCNN của tập con này vào tổng
            totalLCM = (totalLCM + currentLCM) % MOD;
        }

        // Lưu kết quả cho bộ test hiện tại
        results[t] = totalLCM;
    }

    // In ra toàn bộ kết quả sau khi đã xử lý tất cả các test case
    for (int t = 0; t < T; t++) {
        cout << "Case " << t + 1 << ": " << results[t] << endl;
    }

    return 0;
}

Đã sao chép ✔️