CF912E Prime Gift 题解

题目链接：Prime Gift

题意：

给你 \(n\) 个互不相同的素数 \(p_1,p_2,\cdots,p_n\)，它们组成一个集合 \(P\)。

请你求出第 \(k\) 小的正整数，满足该数字的所有素因子 \(\in P\)

\(1\le n\le 16,~2\le p_i\le 100,~\) 保证答案不超过 \(10^{18}\)。

注意到当 \(n=8\) 时，实际上符合条件数并不会很多

考虑 meet in the middle 。我们把 \(P\) 分成比较均匀的两部分 \(A,B\) ，跑 dfs 爆搜两侧的数

接着二分答案，用左侧的某个数 \(A_i\) 去匹配右侧的 \(B_j\) ，扫一遍检验排名。

时间复杂度 \(\mathcal{O}\left(\log V\left(\prod_{p_i \in A} \log_{p_i}V + \prod_{p_i \in B} \log_{p_i}V\right)\right)\) ，其中 \(V\) 是值域。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18 + 5;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(5e6 + 15))

int n, k, cnt1, cnt2, *arr, *cnt, p[66], a[N], b[N];
void dfs(int x, int now)
{
    arr[++(*cnt)] = now; if(x > n) return;
    for(int i = 1; i <= INF / now; i *= p[x])
    {
        dfs(x + 2, now * i);
        if(i > INF / p[x]) break;
    }
}
bool check(int x)
{
    int res = 0, j = cnt2;
    rep(i, 1, cnt1)
    {
        const int t = x / a[i];
        while(j > 0 && b[j] > t) --j;
        res += j;
    }
    return res >= k;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; rep(i, 1, n) cin >> p[i];
    cin >> k; sort(p + 1, p + 1 + n);
    arr = a; cnt = &cnt1; dfs(1, 1);
    arr = b; cnt = &cnt2; dfs(2, 1);
    sort(a + 1, a + 1 + cnt1); cnt1 = unique(a + 1, a + 1 + cnt1) - a - 1;
    sort(b + 1, b + 1 + cnt2); cnt2 = unique(b + 1, b + 1 + cnt2) - b - 1;
    int l = 0, r = INF;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        check(mid) ? r = mid : l = mid + 1;
    }
    cout << l << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/84hvtd5i