5566. 盖楼
约翰计划在农田附近盖一栋H层的高楼。
楼层自下而上依次编号为 1∼H。
为了防止奶牛们集体反对,约翰需要贿赂两头奶牛头目----贝茜和贝蒂。
约翰和两头奶牛约定,在高楼建成后,约翰需要挑选其中的 N 个楼层送给贝茜,M 个楼层送给贝蒂。显然,一个楼层最多只能送给一头奶牛。
贝茜不喜欢能被质数 x 整除的数字,因此它不接受编号能被 x 整除的楼层。
贝蒂不喜欢能被质数 y 整除的数字,因此它不接受编号能被 y 整除的楼层。
请你计算,为了让两头奶牛都能满意从而使得高楼可以顺利搭建,这栋高楼至少需要盖多少层,即请你计算满足条件的 H 的最小可能值。
输入格式
共一行,包含四个整数 N,M,x,y
输出格式
一个整数,表示H的最小可能值。
样例
输入样例1:
3 1 2 3
输出样例1:
5
(二分 + 容斥定理) $O(logn)$
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL N, M, x, y;
bool check(LL mid)
{
LL both = mid - mid / x - mid / y + mid / (x * y); // 都可用的数
LL tx = mid - mid / x - both; // 只有x可用的数
LL ty = mid - mid / y - both; // 只有y可用的数
if(N > tx) both = both - (N - tx);
if(M > ty) both = both - (M - ty);
if(both >= 0) return true;
return false;
}
int main()
{
cin >> N >> M >> x >> y;
LL l = 0, r = 2e9;
while(l < r)
{
LL mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
return 0;
}