远古 vp ZJCPC 的时候的一个题。

定义一个正整数的比较方式：

设两个整数为 \(x,y\) ，把所有质数在 \(x,y\) 质因数分解里的指数分别写出来，按质数升序分别排成两个数组，然后比较这两个数组的字典序。

现给你两个长度 \(10^5\) 的数组 \(A,B\) ，求第 \(k\) 大的 \(A_i*B_j\) ，值域 \(10^6\) 。

显然得筛出来每个数的质因数，然后两个数的积可以直接归并出来。

然后 \(k\) 没限制，一眼二分。

假设二分出了一个值，显然可以 two-pointers 搞出有多少个数比它小。

但是找不到第 \(mid\) 大的值。

于是考虑找出落在 \([l,r]\) 区间的有多少个，然后随机选一个。

这样子复杂度显然有保证，最后二分了一定次数后时最多剩下两个本质不同的值，两个都验一遍即可。

复杂度 \(O(n\times \log n\times \log v)\) 。

使用巨量 stl 的代码被卡爆了。

搬运自 Luogu Blog