Codeforces Round #275 (Div. 2) B Friends and Presents_html/css_WEB-ITnose

题目链接：Friends and Presents

Friends and Presents

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You have two friends. You want to present each of them several positive integers. You want to present cnt1 numbers to the first friend andcnt2 numbers to the second friend. Moreover, you want all presented numbers to be distinct, that also means that no number should be presented to both friends.

In addition, the first friend does not like the numbers that are divisible without remainder by prime number x. The second one does not like the numbers that are divisible without remainder by prime number y. Of course, you're not going to present your friends numbers they don't like.

Your task is to find such minimum number v, that you can form presents using numbers from a set 1,?2,?...,?v. Of course you may choose not to present some numbers at all.

A positive integer number greater than 1 is called prime if it has no positive divisors other than 1 and itself.

Input

The only line contains four positive integers cnt1, cnt2, x, y (1?≤?cnt1,?cnt2?

Output

Print a single integer ? the answer to the problem.

Sample test(s)

input

3 1 2 3

output

input

1 3 2 3

output

Note

In the first sample you give the set of numbers {1,?3,?5} to the first friend and the set of numbers {2} to the second friend. Note that if you give set {1,?3,?5} to the first friend, then we cannot give any of the numbers 1, 3, 5 to the second friend.

In the second sample you give the set of numbers {3} to the first friend, and the set of numbers {1,?2,?4} to the second friend. Thus, the answer to the problem is 4.

大致题意：A有两个朋友B和C，B和C都很喜欢数字，现在A要送给他们各自一些不同的数字来做礼物，但是B不喜欢素数x，所以不能送给他x的倍数；同样如此，C不喜欢素数y，也不能送给他y的倍数。现在的任务是从找到一个最小的数v,使得从1~v里面可以满足A的要求，分别送给B和C。

解题思路：最开始写的时候，用的是暴力枚举，但是结果老是在一个样例上错，可能我的想法不对吧，得不到正确答案。后来看给出的官方解法是用二分。。。想了半天，也没想太明白，关键是想不好怎么用二分呀，该对谁二分，写了这题，又涨姿势了，原来可以从1到无穷大二分，感觉好神奇呀。二分，就要找好二分区间时的条件，根据题目要求，又想了想，才艰难的把这题给搞了。。。

AC代码：

#include #include using namespace std;int main(){//	freopen("in.txt", "r", stdin);	int n, m, x, y;	while(scanf("%d%d%d%d", &n, &m, &x, &y) == 4){		int l = 1, r = 2e9;         //枚举区间端点		while(l < r){               //二分			int mid = l + (r - l)/2;			if( n <= (mid - mid/x)  &&  m <= (mid - mid/y) && n+m <= mid - mid/(x*y))   //划分区间的条件				r = mid;			else			  	l = mid + 1;		}		printf("%d\n", r);		}	return 0;}