Đếm đơn hàng thu được khi khách gọi theo chu kỳ bằng C++

Mô tả bài toán

Văn phòng nhận cuộc gọi mỗi n phút, đơn hàng đến mỗi m phút. Mở cửa z phút. Mỗi cuộc gọi/giao dịch mất 1 phút. Tìm số đơn hàng tối thiểu phải thu để không có đơn chờ khi khách gọi.

Ví dụ

n=1,m=2,z=5 → Cần thu đơn tại phút 2 và 4 → Output: 2.

Thuật toán

Số lần gọi và giao hàng trùng nhau là bội chung nhỏ nhất LCM(n,m). Trong z phút, số lần trùng = z / LCM(n,m). Đó là số đơn phải thu.

Code C++

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

int solve(int n, int m, int z) {
    return z / ( (n * m) / std::gcd(n, m) );
}

int main() {
    int n=1,m=2,z=5;
    cout << solve(n,m,z) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: 1, 2, 5

Output: 2