Tìm bốn ước số của N với tích lớn nhất và tổng bằng N - Tập 2 trong C++

Khái niệm

Cho số nguyên N, tìm tất cả ước số của N và in tích của bốn ước số sao cho tổng bằng N và tích lớn nhất. Nếu không tìm được 4 ước số, in "Không thể". Các ước số có thể bằng nhau.

Đầu vào

N = 60

Đầu ra

Tất cả ước số -> 1 2 3 4 5 6 10 12 15 20 30 60 Tích -> 50625

Chọn ước số 15 bốn lần, 15+15+15+15 = 60, tích lớn nhất.

Phương pháp

Phương pháp trước có độ phức tạp O(P^3) với P là số ước số. Phương pháp hiệu quả O(N^2):

• Lưu tất cả ước số trong container.
• Duyệt tất cả cặp ước số, lưu tổng của chúng trong container khác.
• Đánh dấu chỉ số (element1 + element2) với cặp (element1, element2) để truy ngược.
• Duyệt các tổng cặp, kiểm tra n - pair_sum có tồn tại trong container không, nếu có thì hai cặp tạo thành bộ bốn.
• Dùng mảng hash cặp để lấy các phần tử tạo thành cặp.
• Lưu bộ bốn lớn nhất và in ra.

Ví dụ

// C++ tìm bốn ước số của N với tích lớn nhất và tổng bằng N
#include <bits/stdc++.h>
using namespace std;

void findfactors1(int q){
    vector<int> vec1;
    for (int i = 1; i * i <= q; i++) {
        if (q % i == 0) {
            vec1.push_back(i);
            vec1.push_back(q / i);
        }
    }
    sort(vec1.begin(), vec1.end());
    cout << "Tất cả ước số -> ";
    for (int i = 0; i < vec1.size(); i++)
        cout << vec1[i] << " ";
    cout << endl;
    int maxProduct1 = 1;
    bool flag1 = 1;
    for (int i = 0; i < vec1.size(); i++) {
        for (int j = i; j < vec1.size(); j++) {
            for (int k = j; k < vec1.size(); k++) {
                int y = q - vec1[i] - vec1[j] - vec1[k];
                if (y <= 0) break;
                if (q % y == 0) {
                    flag1 = 0;
                    maxProduct1 = max(vec1[i] * vec1[j] * vec1[k] * y, maxProduct1);
                }
            }
        }
    }
    if (flag1 == 0)
        cout << "Tích -> " << maxProduct1 << endl;
    else
        cout << "Không thể" << endl;
}

int main(){
    int q = 60;
    findfactors1(q);
    return 0;
}

Đầu ra

Tất cả ước số -> 1 2 3 4 5 6 10 12 15 20 30 60 Tích -> 50625