【题解】Prime Gift 二分 CF912E ——quhengyi11

传送门酱：E Prime Gift
题意：给定一个集合
$$S = \{x|x=p_1^{k_1}p_2^{k2}..p_n^{k_n}, k_i \in N_+\}$$
其中 $p_i$是给定的素数，$n<=16$，求这个集合里的第 $k$小元素，保证这个数小于 $10^{18}$

（抱着今天的 CF 网络咕咕+B 题被 Hack 的咕咕心态来补之前的题 QAQ）
首先二分答案是很显然的，验证的话。。。我会 dfs（逃
考虑如何优化验证的过程
我们并不容易发现，我们可以把 16 个数分成两份，然后分别 dfs 记录到两个数组里，接着用双指针来计数就行了。（就是一个 meet in the middle 的思想）
现在就出现了一个问题，怎么分会不超时。
直觉告诉你肯定是平均分成两份舒服啦，而且要分得尽量平均（我的代码是第奇数个数为一组，第偶数个数为一组）
接着就要验证这样分会不会超时的问题。
易知笔算是没有用的，因为上下界差距太悬殊了，根本估不了，只能打代码 dfs
经过验证，8 个因子分别是 $2,5,11,17,23,31,41,47$，所有小于 $10^{18}$的数有 $1119429$个，显然这种复杂度是可以接受的，因此我们就可以码代码了。
看了别的题解还有取前六个小一点的数一组，后 10 个数为一组的搞法，反正只要数字总数能接受就行。
鉴于这种东西并没有有效的用笔计算方法，因此我们要熟练掌握用 meet in the middle 爆搜的方法才能到考试的时候想到这样做。特别是复杂度是指数级别的时候，可以用这样的办法减少一半指数或者给指数开根号（开根号的有一个著名的栗子就是求最大团）
我感觉这篇好水呀 QAQ。。。
代码：

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define N 3000015
#define ll long long
#define up 1e18
#define int long long
int n, c[2][10], cnt1, cnt2;
ll a[N], b[N], tot1, tot2, k;
inline void dfs (bool type, int cnt, ll now, int last)
{
//  printf("%lld\n", tot1);
    if (type) b[++tot2] = now; else a[++tot1] = now;
    fo (i, last, cnt)
        if (now <= up / c[type][i])
            dfs(type, cnt, now * c[type][i], i);
}
inline bool check (ll x)
{
    ll ret = 0;
    int j = std::upper_bound(b + 1, b + tot2 + 1, x) - b - 1;
    fo (i, 1, tot1)
    {
        while (j > 0 && a[i] > x / b[j])
            --j;
        if (!j) break;
        ret += (ll)j;
    }
    return ret < k;
}
main() { 
    scanf("%lld", &n);
    fo (i, 1, n)
    {
        if (i & 1)
            scanf("%lld", &c[0][++cnt1]);
        else
            scanf("%lld", &c[1][++cnt2]);
    }
    scanf("%lld", &k);
    dfs(0, cnt1, 1, 1);
    dfs(1, cnt2, 1, 1);
    std::sort(a + 1, a + tot1 + 1);
    std::sort(b + 1, b + tot2 + 1);
    ll l = 0, r = up + 5, ans = l;
    while (l <= r)
    {
        ll mid = l + r >> 1;
        if (check(mid))
            l = mid + 1;
        else
            r = mid - 1, ans = mid;
    }
    printf("%lld", ans);
    return 0;
}