Codeforces Round #456 (Div. 2) E. Prime Gift（meet-in-the-middle）

本文主要是介绍Codeforces Round #456 (Div. 2) E. Prime Gift（meet-in-the-middle），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://codeforces.com/contest/912/problem/E

开始不太会啊？看了题解发现挺简单的啊？不过他们怎么分析出来每个集合的数目不会特别多的啊。。。窝果然还是个菜鸡啊。。。

把素数分成两个集合，然后暴力搜出来每个集合内的解，然后每次二分结果，合并两个集合的结果就好了，具体就是在X集合枚举，查看Y中有多少数使得X乘Y中的数小于等于mid，排序后双指针即可。

代码：

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const ll INF=1e18;
int n;
ll k;
void dfs(vector<int> &in,vector<ll> &out,int k=0,ll now=1,ll bound=INF)
{if(!bound)return ;if(k>=in.size()){out.pb(now);return;}while(bound){dfs(in,out,k+1,now,bound);now*=in[k];bound/=in[k];}
}
vector<int> in[2];
vector<ll> sX,sY,ss;
bool judge(ll mid)
{ll ret=0;int idy=sY.size()-1;for(int i=0;i<sX.size()&&idy>=0;i++){ll x=sX[i];while(idy>=0&&sY[idy]>mid/x)idy--;ret+=(idy+1);}return ret>=k;
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);in[i%2].pb(x);}scanf("%lld",&k);dfs(in[0],sX);dfs(in[1],sY);sort(sX.begin(),sX.end());sort(sY.begin(),sY.end());ll l=1,r=INF;ll ans=-1;while(l<=r){ll mid=(l+r)>>1;if(judge(mid)){ans=mid;r=mid-1;}else{l=mid+1;}}printf("%lld\n",ans);return 0;
}

这篇关于Codeforces Round #456 (Div. 2) E. Prime Gift（meet-in-the-middle）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---