Hiểu bài toán

Bài toán yêu cầu tìm các số 'đẹp'. Một số được coi là đẹp nếu tổng lập phương của các chữ số của nó là một số nguyên tố. Ví dụ, số 12: 1^3 + 2^3 = 1 + 8 = 9 (không nguyên tố). Số 13: 1^3 + 3^3 = 1 + 27 = 28 (không nguyên tố). Số 10: 1^3 + 0^3 = 1 (không nguyên tố). Đầu vào gồm số lượng truy vấn Q và Q số nguyên dương N (chỉ số). Đầu ra yêu cầu in ra số đẹp thứ N (theo thứ tự tăng dần). Giới hạn: Q <= 1000, N có thể lên tới 10^5. Số tìm kiếm có thể rất lớn, nhưng thực tế số đẹp khá thưa. Phân tích:

• Tổng lập phương của một số X: Nếu X có k chữ số, tổng lập phương tối đa là k * 9^3 = 729k.
• Nếu X > 1000, tổng lập phương < 729*4 = 2916.
• Nếu X > 10000, tổng lập phương < 729*5 = 3645.
• Nếu X rất lớn (vd 10^7), tổng lập phương tối đa là 729*8 = 5832.
• Do đó, chỉ cần kiểm tra các số tổng lập phương trong khoảng [1, 6000] xem có phải số nguyên tố không.
• Ta có thể sinh các số đẹp bằng cách duyệt X từ 1 lên trên, tính tổng lập phương, kiểm tra nguyên tố và lưu vào mảng cho đến khi có đủ số lượng cần thiết (theo yêu cầu N lớn nhất).

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

Cách Brute Force Precomputation (Sàng lọc)

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

const int MAX_N = 100005; // Đủ cho N <= 10^5
const int MAX_SUM = 6000; // Giới hạn tổng lập phương (8 * 729 = 5832)

bool is_prime[MAX_SUM];
vector<int> beautiful;

// Hàm kiểm tra số nguyên tố
void sieve_primes() {
    fill(is_prime, is_prime + MAX_SUM, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < MAX_SUM; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAX_SUM; j += i)
                is_prime[j] = false;
        }
    }
}

// Hàm tính tổng lập phương chữ số
int sum_cubes(int n) {
    int sum = 0;
    while (n > 0) {
        int d = n % 10;
        sum += d * d * d;
        n /= 10;
    }
    return sum;
}

void precompute() {
    sieve_primes();
    // Duyệt số từ 1 đến giới hạn an toàn để tìm đủ số đẹp
    // Số đẹp có thể rất lớn, nhưng tổng lập phương thì nhỏ.
    // Ta cần sinh ra các số đẹp theo thứ tự.
    // Biến i là số đẹp tiềm năng.
    for (int i = 1; beautiful.size() < 100000; i++) {
        int s = sum_cubes(i);
        if (s < MAX_SUM && is_prime[s]) {
            beautiful.push_back(i);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    precompute();

    int q;
    if (cin >> q) {
        while (q--) {
            int n;
            cin >> n;
            cout << beautiful[n - 1] << "\n";
        }
    }
    return 0;
}

• Time Complexity: O(K log log M + N_max * D) (K là giới hạn duyệt số đẹp, M là giới hạn tổng lập phương, D là số chữ số)
• Space Complexity: O(N_max)

Phương pháp này dựa trên nhận định rằng tổng lập phương của một số lớn bị giới hạn ở một giá trị nhỏ (khoảng 6000). Do đó, ta chỉ cần tạo mảng sàng các số nguyên tố trong khoảng [1, 6000]. Sau đó, ta duyệt tuần tự các số tự nhiên (1, 2, 3, ...) để tìm số đẹp. Hàm sum_cubes tính tổng lập phương, và nếu tổng đó là số nguyên tố (kiểm tra qua mảng đã sàng), ta lưu số đó vào danh sách. Duyệt cho đến khi danh sách chứa đủ số lượng số đẹp lớn nhất trong các truy vấn.

Cách Tối ưu hóa nhập xuất và Precomputation

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

const int MAX_PRIME = 6000;
bool prime[MAX_PRIME];
vector<int> res;

// Tính tổng lập phương chữ số
long long calc(long long n) {
    long long s = 0;
    while (n > 0) {
        int d = n % 10;
        s += d * d * d;
        n /= 10;
    }
    return s;
}

void init() {
    // Sàng số nguyên tố
    fill(prime, prime + MAX_PRIME, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i * i < MAX_PRIME; i++) {
        if (prime[i]) {
            for (int j = i * i; j < MAX_PRIME; j += i)
                prime[j] = false;
        }
    }

    // Sinh số đẹp
    // Giả sử N tối đa là 100,000, ta cần tìm 100,000 số đẹp đầu tiên.
    // Số đẹp thứ 100,000 là khoảng 400,000 (thống kê).
    // Duyệt đến 1,000,000 là an toàn tuyệt đối.
    for (long long i = 1; res.size() < 100000; i++) {
        long long sum = calc(i);
        if (prime[sum]) {
            res.push_back(i);
        }
    }
}

int main() {
    // Tối ưu nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Xử lý file
    freopen("BEAUTY3.INP", "r", stdin);
    freopen("BEAUTY3.OUT", "w", stdout);

    init();

    int t;
    if (cin >> t) {
        while (t--) {
            int n;
            cin >> n;
            cout << res[n - 1] << "\n";
        }
    }
    return 0;
}

• Time Complexity: O(10^6) (Thực tế ~ 4*10^5)
• Space Complexity: O(10^5)

Đây là phiên bản tối ưu hóa của phương pháp Precomputation.

1. Tối ưu I/O: Sử dụng ios_base::sync_with_stdio(false); cin.tie(NULL); để tăng tốc độ đọc ghi, quan trọng khi có nhiều truy vấn.
2. Tối ưu sàng số nguyên tố: Chỉ sàng số nguyên tố đến 6000.
3. Giới hạn duyệt: Duyệt số tự nhiên từ 1 đến khoảng 1,000,000 để đảm bảo tìm được đủ 100,000 số đẹp (thực tế số đẹp thứ 100k nằm trong khoảng 400k).
4. Lưu trữ: Mảng res lưu các số đẹp tìm được.

Cách Tối ưu logic sinh số

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

long long f[10000000];

// Kiểm tra số nguyên tố nhanh
bool snt(long long s) {
    if (s == 2 || s == 3) return true;
    if (s % 2 == 0 || s % 3 == 0 || s < 2) return false;
    for (int i = 5; i * i <= s; i += 6) {
        if (s % i == 0 || s % (i + 2) == 0) return false;
    }
    return true;
}

// Tính tổng lập phương
bool sd(long long s) {
    long long tong = 0, t = 0;
    while (s > 0) {
        t = s % 10;
        tong += t * t * t;
        s = s / 10;
    }
    if (snt(tong)) return true;
    return false;
}

int main() {
    // I/O optimization
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    freopen("BEAUTY3.inp", "r", stdin);
    freopen("BEAUTY3.out", "w", stdout);

    long long a, b, c = 0, d, e;

    // Precompute: Duyệt i từ 0 đến 8,000,000
    // Số đẹp thứ 100,000 nhỏ hơn 450,000.
    // Việc duyệt lên 8 triệu là lãng phí nhưng đảm bảo an toàn.
    for (int i = 0; i < 8000000; i++) {
        if (sd(i)) {
            f[c] = i;
            c++;
        }
    }

    if (cin >> a) {
        for (int i = 0; i < a; i++) {
            cin >> d;
            cout << f[d - 1] << endl;
        }
    }
    return 0;
}

• Time Complexity: O(8 * 10^6 * D)
• Space Complexity: O(10^7)

Đây là cách tiếp cận của một bài nộp thực tế (Solution 1). Nó sử dụng mảng toàn cục lớn f[10000000]. Logic cơ bản tương tự: sinh số đẹp và lưu vào mảng.

• Nhận định: Tác giả đã chọn một giới hạn duyệt khá lớn (8 triệu) để đảm bảo bao quát hết các truy vấn có thể có.
• Hàm snt: Viết trực tiếp vòng lặp kiểm tra nguyên tố thay vì dùng sieve, phù hợp với các giá trị tổng lập phương nhỏ.
• Hàm sd: Tính tổng lập phương và gọi snt. Phương pháp này hoạt động tốt do giới hạn thời gian thường rộng cho các bài toán file I/O, nhưng tốn bộ nhớ hơn so với cần thiết.

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

Bài học kinh nghiệm

• Tổng lập phương của một số X có số chữ số k bị giới hạn bởi 9^3 * k. Với X lớn (ví dụ > 1000), tổng lập phương sẽ nhỏ hơn 3000. Điều này có nghĩa là có rất ít số nguyên tố có thể là tổng lập phương. Ta chỉ cần kiểm tra xem một số có phải là số đẹp không bằng cách tính tổng lập phương và kiểm tra tính nguyên tố của nó.
• Bài toán có thể giải quyết bằng cách sinh (generate) các số đẹp trước (offline) và trả lời truy vấn sau (online). Vì số lượng truy vấn lớn và chỉ số N có thể lớn, việc sinh số theo yêu cầu (online) cho từng truy vấn là không hiệu quả.
• Số đẹp thứ 100,000 (N max) có giá trị khoảng 400,000. Do đó, duyệt các số từ 1 đến khoảng 1,000,000 là đủ để tìm ra tất cả các số đẹp cần thiết.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu sai: Tổng lập phương của số lớn có thể vượt quá giới hạn của int (2^31 - 1) nếu số đó có quá nhiều chữ số, mặc dù trong bài này số đẹp thường có ít chữ số. Nên dùng long long cho biến tổng và số kiểm tra.
• Không tối ưu nhập xuất: Với số lượng truy vấn lớn (Q <= 1000), việc không tắt đồng bộ stream trong C++ có thể gây trễ.
• Sai lệch chỉ số: Đề bài yêu cầu số đẹp thứ N, trong khi mảng vector bắt đầu từ index 0. Cần in ra beautiful[n-1].
• Kiểm tra số nguyên tố kém hiệu quả: Với các số nhỏ (< 6000), sàng Eratosthenes hiệu quả hơn nhiều so với duyệt tuần tự.