Bội chung nhỏ nhất

Đề này đọc quen quen, hình như trước đây từng làm rồi. Tìm các số nguyên tố nhỏ hơn 500. Duyệt từng số trong danh sách đã cho, xong phân tích từng số ra thành tích của các số nguyên tố,

sắp xếp và đếm số lượng các số nguyên tố, sau đó cập nhật các số nguyên tố vào danh sách mới.

Danh sách mới sẽ bao gồm các số nguyên tố và số lần xuất hiện. Nếu bất kỳ số nguyên tố nào có số lượng lớn hơn thì cập nhật lại.

Cuối cùng thì tính tích tất cả các số nguyên tố trong danh sách để tìm ra kết quả.

Ví dụ:

danh sách ban đầu là 120, 230, 15, 28

Tách ra thành tích các số nguyên tố:

120 = 2x2x2x3x5

230 = 2x5x23

15 = 3x5

28 = 2x2x7

Khi duyệt 120, danh sách các số nguyên tố và số lượng tương ứng là:

2: 3, 3: 1, 5: 1

tương tự với 230 thì danh sách được cập nhật là:

2: 3, 3: 1, 5: 1, 23:1

với 15:

2: 3, 3: 1, 5: 1, 23: 1

với 28:

2: 3, 3: 1, 5: 1, 7: 1, 23: 1

Cuối cùng, kết quả phải tìm là:

2x2x2 x 3 x 5 x 7 x 23 = 19320.

Bạn thử tham khảo đoạn code sau nhé

#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;
}

Chào bạn! Đừng lo lắng về bài toán Bội Chung Nhỏ Nhất phức tạp này, mình sẽ giúp bạn "xử lý" nó một cách nhẹ nhàng thôi.

Gợi ý:

Để giải quyết bài toán này, bạn có thể sử dụng thư viện GCD (Greatest Common Divisor - Ước chung lớn nhất) và LCM (Least Common Multiple - Bội chung nhỏ nhất). Hầu hết các ngôn ngữ lập trình phổ biến đều có thư viện hỗ trợ tính toán ƯCLN và BCNN.

Hãy nhớ sử dụng các hàm liên quan đến Ước chung lớn nhất và Bội chung nhỏ nhất và duyệt qua tất cả các tập con (trừ tập rỗng) của tập hợp ban đầu.

Ví dụ: Trong Python, bạn có thể sử dụng hàm math.gcd() để tính ƯCLN và tính BCNN dựa trên công thức: lcm(a, b) = (a * b) // gcd(a, b).

Lưu ý: Đừng quên xử lý modulo 10007 để tránh tràn số!

Hy vọng những gợi ý này giúp ích cho bạn. Chúc bạn "code" vui vẻ!