Hiểu bài toán

Cho một số nguyên dương N, yêu cầu tìm số nguyên dương nhỏ nhất (lớn hơn 0) sao cho tích các chữ số của số đó bằng N. Nếu không tồn tại số như vậy, in ra -1. Ví dụ: N=12 thì số cần tìm là 26 (vì 2*6=12 và 26 là số nhỏ nhất có tích bằng 12).

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

Cách Giải thuật tham lam phân tích thừa số (Greedy Factorization)

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        if (n == 1) {
            cout << 1 << endl;
            continue;
        }
        vector<int> digits;
        // Phân tích n thành các thừa số từ 9 về 2
        for (int d = 9; d >= 2; d--) {
            while (n % d == 0) {
                digits.push_back(d);
                n /= d;
            }
        }
        // Nếu n vẫn lớn hơn 1, nghĩa là có thừa số nguyên tố > 9
        if (n != 1) {
            cout << -1 << endl;
        } else {
            // Sắp xếp các chữ số tăng dần để tạo số nhỏ nhất
            sort(digits.begin(), digits.end());
            for (int d : digits) {
                cout << d;
            }
            cout << endl;
        }
    }
    return 0;
}

• Time Complexity: O(log N) - số lượng thừa số tối đa là log2(N)
• Space Complexity: O(log N) - lưu trữ các thừa số

Cách tiếp cận này dựa trên việc phân tích N thành tích các chữ số. Vì muốn số có tích bằng N là nhỏ nhất, ta cần:

1. Phân tích N thành tích các thừa số từ 9 về 2 (thứ tự giảm dần để ưu tiên thừa số lớn nhất)
2. Với mỗi thừa số d, ta chia N cho d cho đến khi không chia được nữa
3. Nếu sau khi chia hết các thừa số từ 2-9 mà N vẫn > 1, nghĩa là N chứa thừa số nguyên tố > 9, không thể tạo ra số có tích bằng N => in -1
4. Các thừa số thu được chính là các chữ số của số cần tìm. Để tạo số nhỏ nhất, ta sắp xếp các chữ số tăng dần.

Ví dụ: N=12

• Duyệt d=9: 12%9≠0
• Duyệt d=8,7,6: 12%6=0 => digits=[6], N=2
• Duyệt d=5,4,3: 12%3≠0
• Duyệt d=2: 2%2=0 => digits=[6,2], N=1
• Sắp xếp digits=[2,6] => in ra 26

Ưu điểm: Đơn giản, hiệu quả, đúng với mọi trường hợp.

Cách Phân tích thừa số với tối ưu hóa

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

string solve(int n) {
    if (n == 0) return "10"; // 1*0=0
    if (n == 1) return "1";  // 1=1

    vector<int> count(10, 0);
    // Phân tích n thành các thừa số từ 9 về 2
    for (int i = 9; i > 1; i--) {
        while (n % i == 0) {
            count[i]++;
            n /= i;
        }
    }

    if (n > 1) return "-1";

    string result = "";
    // Xây dựng số từ các thừa số đã phân tích
    for (int i = 2; i < 10; i++) {
        while (count[i] > 0) {
            result += char('0' + i);
            count[i]--;
        }
    }

    return result.empty() ? "-1" : result;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << solve(n) << '\n';
    }
    return 0;
}

• Time Complexity: O(log N)
• Space Complexity: O(1) - chỉ dùng mảng 10 phần tử

Cách tiếp cận tương tự như cách 1 nhưng tối ưu hơn:

1. Xử lý riêng các trường hợp đặc biệt N=0 và N=1
2. Dùng mảng đếm thay vì vector để lưu số lần xuất hiện của mỗi chữ số
3. Phân tích N thành thừa số từ 9 về 2
4. Nếu N>1 sau phân tích => không có đáp án
5. Xây dựng chuỗi kết quả bằng cách nối các chữ số theo thứ tự tăng dần

Cải tiến: Dùng mảng đếm cố định giúp tiết kiệm bộ nhớ và dễ dàng kiểm soát số lượng mỗi chữ số.

Cách Tối ưu hóa phân tích thừa số

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

long long calc(long long n) {
    if (n == 0) return 10;
    if (n == 1) return 1;

    vector<long long> deck;
    for (long long i = 9; i >= 2; i--) {
        while (n % i == 0) {
            deck.push_back(i);
            n /= i;
        }
    }

    if (n > 1) return -1;
    sort(deck.begin(), deck.end());

    long long res = 0;
    for (long long x : deck) {
        res = res * 10 + x;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        cout << calc(n) << '\n';
    }
    return 0;
}

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

Phiên bản tối ưu hóa với:

1. Sử dụng long long để xử lý số lớn (dù N≤600, nhưng có thể số tạo ra lớn hơn)
2. Tạo số trực tiếp từ các thừa số thay vì in từng chữ số
3. Giữ nguyên logic phân tích thừa số từ lớn đến nhỏ

Lưu ý: Với N=600, số kết quả có thể rất lớn (600 = 2^4 * 3 * 5^2 => số có thể là 2222355). Tuy nhiên, do giới hạn N≤600, số kết quả vẫn nằm trong phạm vi long long.

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

Bài học kinh nghiệm

• Bài toán có thể đổi thành bài toán phân tích N thành tích các thừa số từ 2 đến 9. Nếu phân tích được thì các thừa số chính là các chữ số của số cần tìm.
• Để tạo số nhỏ nhất, cần sắp xếp các thừa số tăng dần sau khi phân tích.
• Nếu N còn lại thừa số nguyên tố > 9 sau khi chia hết cho các số từ 2-9, thì không có đáp án.

Lỗi thường gặp

• Quên xử lý trường hợp N=1 (kết quả là 1, không phải -1)
• Sai thứ tự phân tích: cần duyệt từ 9 về 2 để ưu tiên thừa số lớn nhất, sau đó sắp xếp tăng dần để tạo số nhỏ nhất
• Quên kiểm tra điều kiện n>1 sau vòng lặp phân tích để phát hiện trường hợp không có đáp án