[CF912E] Prime Gift

前言

这道题用到了新的奇技淫巧——折半搜索，所以特地写一写题解加深印象

题目

洛谷

CF

讲解

首先我们通过暴力打表，使用最小的但最多的质数组成([1,10^{18}])中的数，发现约有7e9个数，所以如果暴力枚举，一定会TLE

这个时候当然要考虑二分答案，然后问题就来到了如何check上

折半搜索！

具体的，我们将至多16个数分为尽量平均的两组

对于两组，我们都跑出所有的在([1,10^{18}])中的数

枚举第一个组中所有的数，我们就可以用二分在另一个组中求出答案，最后与外层二分的答案进行比较就行了

具体可以看看代码实现

代码

//12252024832524
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long LL;
const int MAXN = 16;
const int MAXSIZ = 5000005;
int n;
int a[MAXN],b[MAXN],lena,lenb;
LL A[MAXSIZ],B[MAXSIZ],aa,bb,k;

LL Read()
{
	LL x = 0,f = 1;char c = getchar();
	while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
	while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
	return x * f;
}
void Put1(LL x)
{
	if(x > 9) Put1(x/10);
	putchar(x%10^48);
}
void Put(LL x,char c = -1)
{
	if(x < 0) putchar('-'),x = -x;
	Put1(x);
	if(c >= 0) putchar(c);
}
template <typename T>T Max(T x,T y){return x > y ? x : y;}
template <typename T>T Min(T x,T y){return x < y ? x : y;}
template <typename T>T Abs(T x){return x < 0 ? -x : x;}

void dfs1(int x,int MAX,LL val)
{
    if(val != 1) A[++aa] = val;
    for(int i = x;i <= MAX;++ i)
        if(1.0 * val * a[i] <= 1e18)
            dfs1(i,MAX,val*a[i]);
}
void dfs2(int x,int MAX,LL val)
{
    if(val != 1) B[++bb] = val;
    for(int i = x;i <= MAX;++ i)
        if(1.0 * val * b[i] <= 1e18)
            dfs2(i,MAX,val*b[i]);
}
bool check(LL x)
{
    LL ret = 0;
    ret += upper_bound(A+1,A+aa+1,x) - A - 1;
    for(int i = 1;i <= aa;++ i)//内层二分统计个数
    {
        LL dz = upper_bound(B+1,B+bb+1,x/A[i]) - B - 1;
        if(!dz) break;
        ret += dz;
    }
    return ret >= k;//比较
}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    n = Read();
    for(int i = 1;i <= n;++ i)//分组
        if(i & 1) a[++lena] = Read();
        else b[++lenb] = Read();
    k = Read();
    dfs1(1,lena,1); dfs2(1,lenb,1);//分组跑
    A[++aa] = 1;//注意有1，看样例解释！
    sort(A+1,A+aa+1);
    sort(B+1,B+bb+1);//二分的前提当然是要排序
    LL l = 0,r = 1e18,ans = 1e18;
    while(l <= r)//外层二分枚举答案
    {
        LL mid = (l+r) >> 1;
        if(check(mid)) ans = mid,r = mid-1;
        else l = mid+1;
    }
    Put(ans);
	return 0;
}