首页 > 代码库 > Codeforces Round #275 (Div. 2) B

Codeforces Round #275 (Div. 2) B

题目传送门:http://codeforces.com/contest/483/problem/B


题意分析:在1-v的范围内找到一些数分为两个集合,满足第一个集合的元素不能被x整除且个数为cnt1,

第二个集合的元素不能被y整除且个数为cnt2,求最小的v;

二分答案,然后用只满足整除x,只满足整除y和既可整除x又可整除y这三个元素的关系去check一下


代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

int main() {

	long long cnt1, cnt2, x, y;
	cin >> cnt1 >> cnt2 >> x >> y;
	long long l = 0, r = 10000000000, m;
	while (r > l + 1) {
		m = (l + r) / 2;
		if (m - m / x >= cnt1 && m - m / y - max(0LL, cnt1 - m / y + m / (x * y))  >= cnt2)
			r = m;
		else
			l = m;
	}
	cout << r << endl;
	return 0;
}


Codeforces Round #275 (Div. 2) B