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

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