正解:二分+搜索
解题报告:
因为翻译真的很$umm$所以还是写下题目大意$QwQ$,就说给定一个大小为$n$的素数集合,求出分解后只含这些质数因子的第$K$小整数
考虑先把质数分两堆,$meet-in-the-middle$搜出每堆能表示的数.
然后二分答案,扫左边的数看右边有多少个数满足相乘小于等于这个$mid$的,将数量全加起来和$K$比较就成.然后这个查看右边的操作,可以直接一个指针扫下,就不用二分做了$QwQ$.
出于一些不知道原因的玄学原因,在$meet-in-the-middle$的时候最好是两个两个跳着搜,,,直接简单粗暴对半搜会$T$我也不知道啥原理$kk$.
#include<bits/stdc++.h> using namespace std; #define il inline #define gc getchar() #define ll long long #define t(i) edge[i].to #define ri register int #define rc register char #define rb register bool #define rp(i,x,y) for(ri i=x;i<=y;++i) #define my(i,x,y) for(ri i=x;i>=y;--i) #define e(i,x) for(ri i=head[x];i;i=edge[i].nxt) const int N=20+10; const ll mx=1e18; int n,p[N]; ll K; vector<ll>V[2]; il int read() { rc ch=gc;ri x=0;rb y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=gc; if(ch=='-')ch=gc,y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc; return y?x:-x; } void dfs(ll dat,ri nw,ri num) { if(nw>n){V[num].push_back(dat);return;} dfs(dat,nw+2,num);while(dat<=mx/p[nw])dfs(dat*p[nw],nw+2,num),dat=1ll*dat*p[nw]; } il bool check(ll dat) { ri sz=V[0].size(),nw=V[1].size()-1,ret=0; rp(i,0,sz-1){if(V[0][i]>dat || !(~nw))break;while(~nw && V[1][nw]>dat/V[0][i])--nw;ret+=nw+1;} return ret>=K; } int main() { freopen("912e.in","r",stdin);freopen("912e.out","w",stdout); n=read();rp(i,1,n)p[i]=read();K=read();dfs(1,1,1);dfs(1,2,0); sort(V[0].begin(),V[0].end());sort(V[1].begin(),V[1].end()); ll l=1,r=mx;while(l<r){ll mid=(l+r)>>1;if(check(mid))r=mid;else l=mid+1;} printf("%lld ",l); return 0; }