#C240222C. 质因数分解

网址（Website）

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

题解 - 质因数分解 - Super

题解（Solution）

$\qquad$直接暴力 $dfs$ 搜索，可以拿到 $50pts$ 。

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

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

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

$\qquad$注意：

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

$\qquad$2. 判断 $a[l]\times b[r]\le k$ 时可能会爆 $\verb!long long!$，可以转换为判断 $a[l] \le k / b[r]$ 。

代码（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;
}