题目描述
约翰计划在农田附近盖一栋 H
层的高楼。
楼层自下而上依次编号为 1∼H
。
为了防止奶牛们集体反对,约翰需要贿赂两头奶牛头目----贝茜和贝蒂。
约翰和两头奶牛约定,在高楼建成后,约翰需要挑选其中的 N
个楼层送给贝茜,M
个楼层送给贝蒂。
显然,一个楼层最多只能送给一头奶牛。
贝茜不喜欢能被质数 x
整除的数字,因此它不接受编号能被 x
整除的楼层。
贝蒂不喜欢能被质数 y
整除的数字,因此它不接受编号能被 y
整除的楼层。
请你计算,为了让两头奶牛都能满意从而使得高楼可以顺利搭建,这栋高楼至少需要盖多少层,即请你计算满足条件的 H
的最小可能值。
算法1
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int n,m,x,y;
bool cheak(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), s2 = max(0ll, m - b);
return s1 + s2 <= c;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&x,&y);
LL l = 1,r = 6e10;
while(l < r)
{
LL mid = l + r >> 1;
if(cheak(mid))r = mid;
else l = mid + 1;
}
printf("%d",r);
return 0;
}