Bài 1 relax

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

long long a, b, k, m, n;

bool check(long long x) 
{	
	long long asum = (x - x / k) * a;
	long long bsum = (x - x / m) * b;
	
	if ((asum + bsum) >= n) return true;
	else return false;
}

long long BNS() 
{
	long long l = 1, r = min(n / a * 2, n / b * 2) ;

	/* Nếu như nhận xét ban đầu của ta, ta sẽ thực hiện tìm kiếm với l = 1 và r = 1e18;
	   Nhưng vấn đề là giới hạn của a, b <= 1e9, khi nhìn lên hàm check(), trường hợp xấu nhất 
	   ta có thể phải thực hiện phép nhân 1e9 * 1e18 = 1e27 => tràn số vì kiểu long long chỉ lưu đc tối đa tầm 2^64
		
	   Nhận xét 1 : right chỉ cần bằng min của n/a hoặc n/b nếu không tính thời gian nghỉ

	   Nhận xét 2 : Giả sử min(n/a, n/b) = n/a
	   trường hợp xấu nhất : ta sẽ cho a khoảng 2 ngày là nghỉ 1 lần
	   Giả sử n/a = 10 ngày thì thằng a sẽ delay 5 ngày
	   tức khoảng thời gian mà a chặt xong n cây sẽ là 15 ngày
	   để đơn giản hóa bài toán, ta chỉ cần lấy n/a * 2 

	   Nhận xét 3 : Trường hợp a > n thì kết quả của r = 0, do đó ta cần +1 để đảm bảo bài toán luôn đúng :>

	*/
	
	while (l <= r)
	{
		long long mid = (l + r) / 2; 
		if (l == mid || mid == r)
		{
			for (long long i = l; i <= r; i++)
				if (check(i)) return i;
			return 0; 
		}
		
		if (check(mid)) r = mid;
		else l = mid;
	}
	
	return 0;
}

int main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> a >> k >> b >> m >> n;
	
	cout << BNS();

	/*
		Ý TƯỞNG : Tìm kiếm nhị phân

		Trước mắt khi đọc, ta có thể dự đoán được kết quả của bài toán là ngày x sớm nhất 
		để chặt được hết n cây nằm trong khoảng từ : 1 -> 1e18

		Vì vậy, ta sử dụng tìm kiếm nhị phân để tối ưu hóa độ phức tạp lại còn O(log(n))
		Mỗi bước lặp, ta sẽ lấy 1 giá trị mid = (l + r) / 2
		Sau đó ta sẽ kiểm tra giá trị mid xem phải là kết quả của bài toán hay không bằng hàm check(mid)
		Tức là : đến ngày thứ mid thì đã chặt xong n cây hay chưa
		
		nếu số cây chặt được đến ngày thứ mid >= n cây thì ta sẽ thu hẹp giá trị right = mid
		nếu số cây chặt được đến ngày thứ mid < n cây thì ta sẽ thu hẹp giá trị left = mid
	*/
	
	return 0;
}