题意:给定一个大小为\(n(n<=16)\)的素数集合,求出质因数分解后只含这些质数因子的 第\(k\)小整数.集合中的所有素因子不超过\(10^{18}\).保证答案范围不超过\(10^{18}\).
分析:这个折半搜索有点不那么容易想到,毕竟\(n<=16\).
把素数集合分成两个部分,分别爆搜出\(1e18\)范围内 质因数分解后只含这部分质数因子的 数.然后对于搜出来的两个部分从小到大排序之后,二分答案\(mid\),看是否有\(k\)个数对满足乘积小于等于\(mid\)即可.
本题还要注意一下,因为题目保证给出的素数集合是单调递增的.然后折半搜索的优秀时间复杂度基于两个部分是均匀的,所以如果我们直接分成1~n/2和n/2+1~n两个部分来搜,显然第一部分的数会多很多,这样就会超时了.所以我们直接按照下标的奇偶来拆分.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline ll read(){
ll x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
int n,tot1,tot2,p[20];
ll inf=1e18;vector<ll>q1,q2;
inline void dfs1(int now,ll sum){
if(now>n){q1.push_back(sum);++tot1;return;}
for(ll a=1;;a*=p[now]){
dfs1(now+2,sum*a);
if(inf/p[now]<sum*a)break;
//这里要用到除法,乘法会爆long long
}
}
inline void dfs2(int now,ll sum){
if(now>n){q2.push_back(sum);++tot2;return;}
for(ll a=1;;a*=p[now]){
dfs2(now+2,sum*a);
if(inf/p[now]<sum*a)break;
}
}
int main(){
n=read();for(int i=1;i<=n;++i)p[i]=read();
q1.push_back(0);q2.push_back(0);//把0放进去,防止下面尺取的时候下标越界
dfs1(1,1);dfs2(2,1);//折半搜索
sort(q1.begin(),q1.end());sort(q2.begin(),q2.end());//排序
ll k=read(),l=1,r=inf,ans=0;
while(l<=r){//二分答案mid,就是第k大的数
ll mid=(l+r)>>1,tot=0;
for(int i=1,j=tot2;i<=tot1;++i){
while(j&&mid/q1[i]<q2[j])--j;//这里要用到除法,乘法会爆long long
tot+=j;
}
if(tot<k)l=mid+1;//如果没有k个数对满足相乘小于等于mid,说明mid小了
else ans=mid,r=mid-1;
}
printf("%lld\n",ans);
}