题意 : 给你 N ( 1 ≤ N ≤ 16 ) 个质数，然后问你由这些质数作为因子的数 ( 此数不超 10^18 ) & ( 不一定需要其因子包含所给的所有质数 ) 的第 k 个是什么
分析 :
由于各项的数据范围都太过于大，所以考虑从比较小的 N 入手
由于 N 比较小，所以可以先到是否能折半枚举，先将质数分成两个集合
然后分别处理出两个集合的所有不超过 10^18 次方的以集合内的数作为因子的数（DFS可以构造）
最后这些数的个数貌似是可以接受的，至于证明貌似出题人也在题解评论下面说可以暴力跑一下看看 ( 误
分成两个集合处理完之后将两个集合排序，接下来的工作就是上下界分别为 0 和 10^18 去二分答案
二分的判断函数需要做到==>给出一个数，然后判断在两个有序数组元素两两乘积里面排第几
这里可以用一个双指针技巧 O(N) 地做到
先从大到小枚举其中一个集合，那么 (当前二分数) / (第一集合的数) 这个商是越来越大的
而当满足 (第二集合的数) ≤ (当前二分数) / (第一集合的数) 那么说明有一个乘积在当前二分数的后面
由于不等式右边是逐渐增大的，所以只要我们从小到达枚举第二集合的数，即可下次不必从头开始判断
因此是 O(N) 的，可能需要看一下代码有助于理解。
#include<bits/stdc++.h> #define LL long long using namespace std; const LL INF = 1e18; vector<long long> vet[2]; int N, num[20]; LL K; ///DFS构造以集合内质数为因子的数，注意DFS的写法，可以做到不重复 void DFS(int L, int R, LL val, const int idx) { vet[idx].push_back(val); for(int i=L; i<=R; i++) if(INF / (LL)num[i] >= val) DFS(i, R, val*(LL)num[i], idx); } LL Order(LL NUM) { int j = 0; LL cnt = 0; for(int i=vet[0].size()-1; i>=0; i--){///双指针技巧 while(j < vet[1].size() && vet[1][j] <= NUM / vet[0][i])///不等式右边是逐渐变大的 j++; cnt += j; } return cnt; } int main(void) { scanf("%d", &N); for(int i=1; i<=N; i++) scanf("%d", &num[i]); scanf("%I64d", &K); sort(num+1, num+1+N); for(int i=1,j=N; i<j; i+=2,j-=2) swap(num[i], num[j]); DFS(1, min(6, N), 1, 0); DFS(min(6, N)+1, N, 1, 1); sort(vet[0].begin(), vet[0].end()); sort(vet[1].begin(), vet[1].end()); LL L = 0, R = INF, mid, ans; while(L <= R){ mid = L + ((R - L)>>1); if(Order(mid) < K) L = mid + 1; else R = mid - 1; } return !printf("%I64d ", R + 1); }