Codeforces 912E Prime Gift（预处理 + 双指针 + 二分答案）

题目链接 Prime Gift

题意给定一个素数集合，求第k小的数，满足这个数的所有质因子集合为给定的集合的子集。

保证答案不超过$10^{18}$

考虑二分答案。

根据折半的思想，首先我们把这个集合的数分成两组。

然后分别生成这两组质数所能表示出的正整数的集合。

然后把这个集合sort一下，我们得到了两个有序的数列。

在计算小于等于某个数$x$的符合题目条件的数的时候，我们枚举第一个集合中的数，

用双指针定位和当前枚举到的数乘积恰好小于等于$x$的位置。

然后累加。

这里有一个细节，我们要保证两个正整数的集合的大小要尽可能接近。

所以分组方式要稍微讲究一下，

我这里先对整个数列sort，再根据位置的奇偶性把整个数列分成两组。

这道题的极限数据的集合应该是前$16$小的质数……

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

typedef long long LL;

const int N = 63;

int n;

int cnt;

LL a[N], c[N], k, l, r;

vector <LL> s[2];

void dfs(int i, int x, LL now){

	s[i].push_back(now);

	rep(j, x, cnt) if (1e18 / c[j] >= now) dfs(i, j, now * c[j]);

}

LL solve(LL x){

	int j = 0;

	LL ret = 0;

	dec(i, s[0].size() - 1, 0){

		while (j < s[1].size() && s[1][j] <= x / s[0][i]) ++j;

		ret += j;

	}

	return ret;

}

int main(){

	scanf("%d", &n);

	rep(i, 1, n) scanf("%lld", a + i);

	sort(a + 1, a + n + 1);

	scanf("%lld", &k);

	cnt = 0;

	rep(i, 1, n) if (i & 1) c[++cnt] = a[i];

	dfs(0, 1, 1);

	cnt = 0;

	rep(i, 1, n) if (!(i & 1)) c[++cnt] = a[i];

	dfs(1, 1, 1);

	sort(s[0].begin(), s[0].end());

	sort(s[1].begin(), s[1].end());

	l = 1, r = 1e18;

	while (l + 1 < r){

		LL mid = (l + r) / 2;

		if (solve(mid) >= k) r = mid;

		else l = mid + 1;

	}

	if (solve(l) >= k) printf("%lld\n", l);

	else printf("%lld\n", r);

	return 0;

}

巴特西

Codeforces 912E Prime Gift（预处理 + 双指针 + 二分答案）

最新文章

热门文章