Hiểu bài toán

Bài toán yêu cầu tìm số lượng số composite (số nguyên dương lớn hơn 1 và không phải số nguyên tố) nhiều nhất có thể sao cho tổng của chúng bằng N. Nếu không thể, in ra -1. Với N lớn (lên tới 10^18), chúng ta cần một công thức toán học thay vì duyệt.

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

Cách Phân tích theo số dư (Modulo 4)

#include <iostream>
using namespace std;

typedef long long ll;

ll solve(ll N) {
    if (N < 4) return -1;
    // Nếu chia hết cho 4, dùng toàn bộ số 4
    if (N % 4 == 0) return N / 4;

    // Nếu dư 1: 4k + 1. Phải dùng 9 (4+5) thay cho 4+1. 
    // Điều kiện: N >= 9 (tức k >= 2)
    if (N % 4 == 1) {
        if (N < 9) return -1;
        return (N - 9) / 4 + 1;
    }

    // Nếu dư 2: 4k + 2. Phải dùng 6 (4+2).
    // Điều kiện: N >= 6 (tức k >= 1)
    if (N % 4 == 2) {
        if (N < 6) return -1;
        return (N - 6) / 4 + 1;
    }

    // Nếu dư 3: 4k + 3. Phải dùng 15 (9+6) hoặc 9+4+4?
    // Phân tích: 3 = 3 (không dùng được). Phải dùng thêm số khác.
    // Cách 1: Dùng 15 (9+6). N >= 15. Số lượng: 1 (cho 15) + (N-15)/4.
    // Cách 2 (tối ưu hơn): Dùng 9 (từ phần dư 1) và 6 (từ phần dư 2).
    // Thực tế: (N-9-6) = 4k - 12 = 4(k-3). Cần k >= 3 => N >= 15.
    // Công thức Solution 3: (N - 15) / 4 + 2.
    if (N % 4 == 3) {
        if (N < 15) return -1;
        return (N - 15) / 4 + 2;
    }
    return -1;
}

int main() {
    int q;
    cin >> q;
    while (q--) {
        ll n;
        cin >> n;
        cout << solve(n) << endl;
    }
}

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

Đây là phương pháp tối ưu dựa trên quan sát các số composite nhỏ nhất là 4, 6, 9, 15... Để tạo tổng N với số lượng thành phần nhiều nhất, ta nên ưu tiên dùng số 4 (nhỏ nhất).

1. Nếu N chia hết cho 4: Dùng toàn bộ số 4.
2. Nếu N chia 4 dư 1: Ta không thể tạo dư 1 từ các số chẵn hoặc 9. Giải pháp là thay một cặp (4, 4) bằng (4, 9) tổng cộng 13, chia 4 dư 1. Điều này có nghĩa là dùng 1 số 9 và phần còn lại là các số 4. Điều kiện N >= 9.
3. Nếu N chia 4 dư 2: Tương tự, thay một số 4 bằng 6. Dùng 1 số 6 và phần còn lại là các số 4. Điều kiện N >= 6.
4. Nếu N chia 4 dư 3: Ta có thể dùng 1 số 9 và 1 số 6 (tổng 15, chia 4 dư 3). Phần còn lại là các số 4. Điều kiện N >= 15.

Cách Công thức tổng quát (Solution 3)

#include <iostream>
using namespace std;

long long solve(long long N) {
    if (N < 4) return -1;
    if (N == 5) return -1;
    if (N == 7) return -1;
    if (N == 11) return -1;

    long long r = N % 4;
    if (r == 0) return N / 4;
    if (r == 1) return (N - 9) / 4 + 1;
    if (r == 2) return (N - 6) / 4 + 1;
    if (r == 3) return (N - 9 - 6) / 4 + 2;
    return -1;
}

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

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

Đây là biến thể của phương pháp Modulo 4, kiểm tra các trường hợp đặc biệt nhỏ (5, 7, 11) sau đó áp dụng công thức.

• Dư 0: N/4.
• Dư 1: (N-9)/4 + 1.
• Dư 2: (N-6)/4 + 1.
• Dư 3: (N-15)/4 + 2. Các số 5, 7, 11 là các số không thể biểu diễn (5 = 4+1, 7 = 4+3, 11 = 4+4+3) nhưng N >= 4. Sau 11, mọi số đều có thể biểu diễn.

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

Bài học kinh nghiệm

• Số composite nhỏ nhất và hiệu quả nhất để tạo tổng là 4.
• Các số dư khi chia cho 4 có thể được xử lý bằng cách thay thế các số 4 bằng các số composite khác như 6, 9, 15.
• Tất cả các số nguyên dương N >= 12 đều có thể biểu diễn thành tổng các số composite (theo biến thể của bài toán Thue-Morse/coin change với các đồng xu 4, 6, 9).

Lỗi thường gặp

• Quên kiểm tra các trường hợp N nhỏ (N < 4, N = 5, N = 7, N = 11) mà công thức tổng quát có thể sai.
• Sử dụng số nguyên 32-bit thay vì 64-bit (long long)导致 overflow khi xử lý N lên tới 10^18.