CodeforcesRound#275(Div.2)BFriendsandPresents_html/css

Friends and Presents

time limit per test

memory limit per test

input

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;}

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com