题目描述
约翰计划在农田附近盖一栋 H 层的高楼。
楼层自下而上依次编号为 1∼H。
为了防止奶牛们集体反对,约翰需要贿赂两头奶牛头目----贝茜和贝蒂。
约翰和两头奶牛约定,在高楼建成后,约翰需要挑选其中的 N 个楼层送给贝茜,M 个楼层送给贝蒂。
显然,一个楼层最多只能送给一头奶牛。
贝茜不喜欢能被质数 x 整除的数字,因此它不接受编号能被 x 整除的楼层。
贝蒂不喜欢能被质数 y 整除的数字,因此它不接受编号能被 y 整除的楼层。
请你计算,为了让两头奶牛都能满意从而使得高楼可以顺利搭建,这栋高楼至少需要盖多少层,即请你计算满足条件的 H 的最小可能值。
输入格式
共一行,包含四个整数 N,M,x,y。
输出格式
一个整数,表示 H 的最小可能值。
数据范围
前 3 个测试点满足 1≤N,M≤10。
所有测试点满足 1≤N,M<109,N+M≤109,2≤x<y≤30000,保证 x,y 均是质数。
样例
输入样例1:
3 1 2 3
输出样例1:
5
输入样例2:
1 3 2 3
输出样例2:
4
算法1
(二分) $O(log_2n)$
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int n,m,x,y;
bool chk(LL h)
{
LL a=h/y-h/x/y;
LL b=h/x-h/x/y;
LL c=h-h/x-h/y+h/x/y;
LL s1=max(0ll,n-a);
LL s2=max(0ll,m-b);
return s1+s2<=c;
}
int main()
{
cin>>n>>m>>x>>y;
LL l=1,r=1e18;
while(l<r)
{
LL mid=l+r>>1;
if(chk(mid))r=mid;
else l=mid+1;
}
cout<<r<<endl;
return 0;
}