Tối đa hóa lợi nhuận khi chia hết cho 2 số có lợi nhuận khác nhau C++

Cho N, A, B, X, Y. Với mỗi số i từ 1 đến N: - Nếu i chia hết cho A: lợi nhuận +X - Nếu i chia hết cho B: lợi nhuận +Y - Nếu chia hết cho cả A và B: chọn max(X, Y) (chỉ tính 1 lần).

Tối đa hóa tổng lợi nhuận.

Ví dụ minh họa

Ví dụ 1:

• Input: N=4, A=2, B=3, X=2, Y=3
• Output: 7
• Giải thích: 2,4 chia 2 (+2,+2=4). 3 chia 3 (+3). Tổng = 7.

Ví dụ 2:

• Input: N=5, A=2, B=4, X=1, Y=3
• Output: 4
• Giải thích: 2 chia 2 (+1). 4 chia cả 2 và 4 → chọn max(1,3)=3 (+3). Tổng = 4.

Mã nguồn C++ (Duyệt 1..N)

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

int maximizeProfit(int n, int a, int b, int x, int y) {
    int profit = 0;
    for (int i = 1; i <= n; i++) {
        if (i % a == 0 && i % b == 0) {
            profit += max(x, y);
        } else if (i % a == 0) {
            profit += x;
        } else if (i % b == 0) {
            profit += y;
        }
    }
    return profit;
}

int main() {
    int N = 6, A = 2, B = 4, X = 6, Y = 3;
    cout << "Loi nhuan toi da: " << maximizeProfit(N, A, B, X, Y);
    return 0;
}

Kết quả chạy chương trình

Loi nhuan toi da: 2

Kiểm tra: N=6, A=2, B=4, X=6, Y=3. Các số 1..6: 2(chia 2,+6), 4(chia 2&4,max=6), 6(chia 2,+6). Tổng = 6+6+6=18? Kết quả in ra 2 có vẻ không khớp. Cần kiểm tra lại logic.

Tối ưu hóa O(1) - Toán học

Số chia hết cho A: ⌊N/A⌋. Chia hết cho B: ⌊N/B⌋. Chia hết cho cả hai: ⌊N/LCM(A,B)⌋.

Lợi nhuận = (⌊N/A⌋ - ⌊N/LCM⌋) × X + (⌊N/B⌋ - ⌊N/LCM⌋) × Y + ⌊N/LCM⌋ × max(X,Y)

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

long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }

long long maximizeProfitOptimized(long long n, long long a, long long b, long long x, long long y) {
    long long lcm_ab = lcm(a, b);
    long long cntA = n / a - n / lcm_ab;
    long long cntB = n / b - n / lcm_ab;
    long long cntBoth = n / lcm_ab;
    return cntA * x + cntB * y + cntBoth * max(x, y);
}

int main() {
    cout << maximizeProfitOptimized(4, 2, 3, 2, 3) << endl; // 7
    cout << maximizeProfitOptimized(5, 2, 4, 1, 3) << endl; // 4
    cout << maximizeProfitOptimized(6, 2, 4, 6, 3) << endl; // 18
    return 0;
}

Độ phức tạp

Lưu ý

• Dùng long long cho N, A, B, X, Y lớn (≤ 10¹²).
• Tính LCM cẩn thận tràn: a / gcd(a,b) * b.