Hiểu bài toán

Bài toán yêu cầu tìm số họ hàng thứ n, trong đó một số được gọi là 'số họ hàng' nếu nó chỉ chứa các thừa số nguyên tố là 2, 3 và 5 (tức là số的形式 là 2^a * 3^b * 5^c với a, b, c là số tự nhiên). Ví dụ, 100 = 2^2 * 5^2 là một số họ hàng. Ta cần in ra số họ hàng thứ n (với n <= 2000). Dãy số này tương tự bài toán 'Ugly Numbers' (Số ugly).

Các cách tiếp cận

Cách Sử dụng Set (Duyệt đệ quy)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    set<long long> s;
    s.insert(2);
    s.insert(3);
    s.insert(5);

    long long h = 0;
    vector<int> p = {2, 3, 5};

    for (int i = 1; i <= n; ++i) {
        h = *s.begin();
        s.erase(s.begin());

        for (int m : p) {
            s.insert(h * m);
        }
    }

    cout << h << endl;

    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Cách tiếp cận này sử dụng một Set để lưu trữ các số họ hàng. Ban đầu chèn 2, 3, 5 vào set. Sau đó, ta thực hiện lặp n lần để tìm số thứ n. Ở mỗi bước, ta lấy số nhỏ nhất trong set (sử dụng iterator begin), đó chính là số họ hàng tiếp theo. Sau đó, ta nhân số đó với 2, 3, 5 và chèn vào set. Set sẽ tự động duy trì thứ tự và loại bỏ trùng lặp. Ví dụ, số 6 có thể được tạo từ 23 hoặc 32, nhưng set chỉ lưu một lần.

Độ phức tạp: O(n log n) vì mỗi thao tác chèn/xóa trong set mất O(log k) (k là số phần tử trong set, k ~ n), và ta lặp n lần. Không gian O(n) để lưu các số.

Cách Sử dụng BFS/Deque (Duyệt)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    if (!(cin >> n)) return 0;

    vector<long long> v;
    v.push_back(1);

    int i2 = 0, i3 = 0, i5 = 0;

    while (v.size() <= n) {
        long long next2 = v[i2] * 2;
        long long next3 = v[i3] * 3;
        long long next5 = v[i5] * 5;
        long long next_val = min({next2, next3, next5});

        v.push_back(next_val);

        if (next_val == next2) i2++;
        if (next_val == next3) i3++;
        if (next_val == next5) i5++;
    }

    cout << v[n] << endl;
    return 0;
}
// Nguồn tham khảo: Solution 3 (cải tiến)

• Time Complexity: O(n)
• Space Complexity: O(n)

Đây là cách tối ưu hóa từ phương pháp dùng Set. Thay vì dùng Set (tốn log n), ta dùng một Vector và 3 con trỏ (i2, i3, i5). Vector v lưu trữ các số họ hàng đã tìm thấy theo thứ tự tăng dần. Ban đầu v = {1}. Ta duy trì 3 chỉ số i2, i3, i5. Vị trí i2 trỏ tới phần tử trong v mà khi nhân với 2 sẽ tạo ra số mới lớn hơn số gần nhất đã thêm. Tương tự cho i3 và i5. Trong mỗi bước:

1. Tính next2 = v[i2] * 2, next3 = v[i3] * 3, next5 = v[i5] * 5.
2. Tìm giá trị nhỏ nhất trong 3 giá trị trên.
3. Thêm giá trị nhỏ nhất đó vào v.
4. Cập nhật chỉ số i2, i3, i5 tương ứng nếu số vừa thêm bằng next2, next3, hoặc next5 (nếu bằng nhiều hơn một thì cập nhật tất cả). Ví dụ: khi thêm 6, nó bằng next2 (32) và next3 (23), cả i2 và i3 đều tăng.

Độ phức tạp: O(n) thời gian (chỉ lặp n lần, mỗi lần thao tác hằng số) và O(n) bộ nhớ.

Cách Brute Force (Tạo trước)

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long LIM = 1e18; // Giới hạn đủ lớn
    vector<long long> v;

    // Duyệt các mũ của 2, 3, 5
    for (int i = 0; i <= 59; i++) {
        long long p2 = 1LL << i; // Tính 2^i
        if (p2 > LIM) break;
        for (int j = 0; j <= 37; j++) {
            long long p3 = 1;
            for(int k=0; k<j; k++) p3 *= 3;
            if (p2 > LIM / p3) break;
            for (int k = 0; k <= 25; k++) {
                long long p5 = 1;
                for(int l=0; l<k; l++) p5 *= 5;
                if (p2 > LIM / p3 / p5) break;
                v.push_back(p2 * p3 * p5);
            }
        }
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    int n;
    cin >> n;
    cout << v[n-1] << endl;
}

• Time Complexity: O(K log K)
• Space Complexity: O(K)

Phương pháp này tạo ra tất cả các số họ hàng có thể nhỏ hơn một giới hạn rất lớn (ví dụ 10^18), sau đó sắp xếp và chọn ra số thứ n. Ta duyệt ba vòng lặp lồng nhau để tạo các kết hợp của 2^a, 3^b, 5^c. Với n <= 2000, số họ hàng thứ 2000 nằm trong khoảng 10^9, nên giới hạn 10^18 là an toàn. Sau khi tạo xong danh sách, ta sắp xếp và loại bỏ trùng lặp (nếu có). Phương pháp này cồng kềnh hơn và tốn bộ nhớ hơn hai phương pháp trên, nhưng đảm bảo đúng nếu giới hạn được chọn đủ lớn.

Độ phức tạp: Phụ thuộc vào số lượng tổ hợp (khoảng 604030 ~ 72,000), sau đó là sort O(K log K).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán là bài toán kinh điển 'Ugly Numbers'.
• Các số 'họ hàng' được sinh ra bằng cách nhân các số đã có sẵn với 2, 3, 5.
• Phương pháp tối ưu nhất (O(n)) sử dụng 3 con trỏ (hoặc 3 hàng đợi ưu tiên) để đảm bảo sinh ra dãy số theo thứ tự tăng dần mà không cần dùng cấu trúc dữ liệu phức tạp như Set.

Lỗi thường gặp

• Sử dụng số nguyên 32-bit (int) để lưu trữ kết quả vì số họ hàng thứ 2000 lớn hơn 10^9, cần dùng kiểu long long (64-bit).
• Tạo ra các số trùng lặp nếu không kiểm soát tốt thứ tự sinh (ví dụ sinh 6 từ 23 và 32). Các phương pháp dùng Set hay Vector + 3 con trỏ đều tự động xử lý vấn đề này.
• Nếu dùng đệ quy/quay lui kết hợp với Set để sinh số, cần chú ý giới hạn giá trị (nên cắt tỉa khi số quá lớn) để tránh tràn bộ nhớ hoặc thời gian.