Tối đa hóa tích 4 ước số của một số N trong C++

Cho số N. Nhiệm vụ: tìm 4 ước số A, B, C, D của N sao cho:

• A + B + C + D = N
• Tích A × B × C × D lớn nhất.

Ví dụ 1

Input – N = 10

Output – 20

Giải thích: Ước của 10: 1, 2, 5, 10. Chọn 5, 2, 2, 1 → Tổng = 10, Tích = 20.

Ví dụ 2

Input – N = 16

Output – 256

Giải thích: Ước của 16: 1, 2, 4, 8, 16. Chọn 4, 4, 4, 4 → Tổng = 16, Tích = 256.

Thuật toán

1. Tìm tất cả ước số của N (duyệt đến √N).
2. Thử tất cả tổ hợp 4 ước số (cho phép lặp) từ tập ước số.
3. Kiểm tra tổng = N, cập nhật tích max.

Lưu ý: Số ước số của N ≤ 10^5 là rất nhỏ (~1000), nên 4 vòng lặp lồng nhau O(d^4) vẫn chạy nhanh (d = số ước).

Ví dụ code

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

vector<int> getFactors(int N) {
    vector<int> factors;
    for (int i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            factors.push_back(i);
            if (i != N / i) factors.push_back(N / i);
        }
    }
    return factors;
}

int maxProductFourFactors(int N) {
    vector<int> factors = getFactors(N);
    int maxProd = 0;
    
    // Thử tất cả 4 ước (cho phép trùng)
    for (int a : factors)
        for (int b : factors)
            for (int c : factors)
                for (int d : factors) {
                    if (a + b + c + d == N) {
                        maxProd = max(maxProd, a * b * c * d);
                    }
                }
    return maxProd;
}

int main() {
    int N = 10;
    cout << "Maximum product: " << maxProductFourFactors(N) << endl;
    return 0;
}

Kết quả

Maximum product: 20

Tối ưu hóa: Có thể sắp xếp ước số và dùng 3 vòng lặp + binary search cho ước thứ 4, hoặc dùng quy hoạch động. Nhưng với d ≤ ~1000, O(d^4) ≈ 10^12 quá chậm. Cần tối ưu: O(d^3 log d) hoặc O(d^2) với 2-sum.

Cách tốt hơn (O(d^2)): Tính tất cả tổng cặp 2 ước số → map[tổng] = max tích cặp đó. Sau đó tìm 2 cặp có tổng = N.