Codeforces 912 E.Prime Gift (折半枚举、二分)

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目链接：Prime Gift

题意：

给出了n(1<=n<=16)个互不相同的质数pi(2<=pi<=100)，现在要求第k大个约数全在所给质数集的数。(保证这个数不超过1e18)

题解：

如果暴力dfs的话肯定超时间，其实给的n数据范围最大是16是一个很奇妙的数(一般折半枚举基本上是这样的数据范围@。@～)。所以想到折半枚举，把所有的质数分成两份求出每份中所有小于1e18的满足条件的数。然后二分答案，写cheak函数时遍历第一个集合，对第二个集合二分(折半枚举基本上这个套路)。但是，这里一定要注意的是这里折半枚举指的并不是将n分成两份求出两个集合，而是要让分出的两份数所形成的集合中所含的个数接近，因为用较小的数形成的集合个数要多很多(被这个点卡了好久#。#）。

 #include<bits/stdc++.h>

 using namespace std;

 const int MAX_N = 1e4+;

 const long long INF = 1e18;

 long long N,M,T,k;

 long long vec[][MAX_N];

 vector<long long> st[];

 void dfs(int l,int r,long long rt,int id)

 {

     st[id].push_back(rt);

     for(int i=l;i<r;i++)

     {

         if(INF/vec[id][i] >= rt)

             dfs(i,r,rt*vec[id][i],id);

     }

 }

 long long cheak_num(long long x)

 {

     long long ans = ;

     for(int i=;i<st[].size();i++)

     {

         if(st[][i] )

         ans += upper_bound(st[].begin(),st[].end(),x/st[][i]) - st[].begin();

     }

     return ans;

 }

 int main()

 {

     while(cin>>N)

     {

         st[].clear();st[].clear();

         for(int i=;i<min((long long),N);i++) scanf("%lld",&vec[][i]);

         for(int i=;i<N-min((long long),N);i++) scanf("%lld",&vec[][i]);

         dfs(,min((long long),N),,);

         dfs(,N-min((long long),N),,);

         for(int i=;i<;i++)

             sort(st[i].begin(),st[i].end());

         cin>>k;

         long long l=,r=INF;

         while(l<=r)

         {

             long long mid = (l+r)>>;

             if(cheak_num(mid) < k) l = mid+;

             else r = mid-;

         }

         cout<<l<<endl;

     }

     return ;

 }

 /*

 16

 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53

 755104793

 */