CodeForces 912E Prime Gift
题目大意
给定有NNN个素数的集合(1≤N≤161\le N\le 161≤N≤16)，要求用集合内的素数通过乘法构造出一些数字，并输出这些数字中的第KKK大。
注意一个素数可以多次使用，且答案不超过101810^{18}1018。
分析
注意到N≤16N\le 16N≤16，这意味着我们可以采用爆搜。
但直接搜索似乎不太好做。考虑中途相遇法：
我们将整个集合划分为两部分，对于集合中的素数爆搜出它们能够组合出的所有数。
然后考虑答案求解。发现直接得到第KKK大的数似乎有点困难，于是考虑二分。
这样一来问题就转化为了给定一个数和两个数列，求这个数在两个序列中任选两个数乘起来得到的序列中的排名。
这个东西用双指针做一做就可以了。
注意不能直接将序列中的两个数乘起来，我们必须将乘法转化为除法。
参考代码
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;typedef long long ll;
const int Maxn = 16;
const ll INF = 1e18;int N, p[Maxn + 5];
ll K;vector<ll> val[2];
void DFS(int typ, int x, ll now) {
val[typ].push_back(now);for(int i = x; i <= N; i += 2)if(INF / p[i] >= now) DFS(typ, i, now * p[i]);
}bool check(ll x) {
ll rnk = 0;for(int i = (int)val[0].size() - 1, j = 0; i >= 0; i--) {
while(j < (int)val[1].size() && val[1][j] <= x / val[0][i])++j;rnk += j;}return rnk >= K;
}int main() {
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifscanf("%d", &N);for(int i = 1; i <= N; i++)scanf("%d", &p[i]);scanf("%lld", &K);sort(p + 1, p + N + 1);DFS(0, 1, 1);DFS(1, 2, 1);sort(val[0].begin(), val[0].end());sort(val[1].begin(), val[1].end());ll lb = 1, ub = INF;ll ans;while(lb <= ub) {
ll mid = (lb + ub) >> 1;if(check(mid)) ub = mid - 1, ans = mid;else lb = mid + 1;}printf("%lld\n", ans);return 0;
}