#C240222C. 质因数分解

网址（Website）

题目详情 - 质因数分解 - Super

题解 - 质因数分解 - Super

题解（Solution）

直接暴力搜索，可以拿到。

从部分分中获得提示，这里的翻了两倍，虽然我们无法处理的情况，但是处理两个的情况还是绰绰有余，因此想到了折半搜索。（我自己都不知道这玩意儿，考场上就更不可能想到了）

我们求出了和两个区间内部的“好数”有哪些，用记录下来并排序，最终的“好数”其实就是这两个中的数字两两相乘得到的集合与这两个的并集。（由于两个中的质因数互不相同，所以不会出现重复的情况）。

发现，说明要在或者的时间复杂度内求出答案，大数据很容易联想到二分答案，求出当前对应的排名，与作比较，就可以得出答案。
排名该怎么求呢？我们将计算出来的两个记为数组和数组，由于都已经排好序，我们可以用双指针求排名。设代表数组的开头，代表数组的末尾。枚举中的元素，在中元素逐渐变大的时候，若要继续满足，的位置就要往前走，对于每个记录满足条件的有多少个就好啦~

注意：

1. 如果数组或数组中全部是大数字，很可能影响最终的结果（容易爆），所以可以先排序，再交换序列中的奇数位，使左右数的大小尽量平均。

2. 判断时可能会爆，可以转换为判断。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 36; 

int n,k,a[N];

vector<int> vec[2];

void dfs_vec(int l,int r,int v,int op){
	if(l==r+1) return vec[op].emplace_back(v),void();
	if(inf/a[l] >= v) dfs_vec(l,r,v*a[l],op);
	dfs_vec(l+1,r,v,op);
}

inline bool chk(int mid){
	int rank = 0,r = vec[0].size()-1;
	for(int l=0;l<vec[1].size() && ~r;l++){
		while(r>=0 && vec[1][l] > mid / vec[0][r]) r--;
		rank += r+1;
	}return rank >= k;
}

void Solve(){
	sort(a + 1,a + n + 1);
	For(i,1,n/2) if(i&1) swap(a[i], a[i+n/2]); 
	
	dfs_vec(1,n/2,1,0), dfs_vec(n/2+1,n,1,1);
	sort(vec[0].begin(),vec[0].end());
	sort(vec[1].begin(),vec[1].end());
	
	int l=1,r=inf,ans=-1;
	while(l<=r){
		int mid = l+r>>1;
		if(chk(mid)) ans=mid, r=mid-1;
		else l=mid+1;
	}cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("prime");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	cin>>n;For(i,1,n) a[i]=input();cin>>k; 
	int Tim = clock();Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}