简要题意
记 \(p_i\) 为从小到大第 \(i\) 个质数，并记 \(v_p(n)\) 为正整数 \(n\) 中质因子 \(p\) 的最高次幂（ \(p\nmid n\) 则为 \(0\) ）。现在对于两个正整数 \(x,y\)，重新定义它们的大小关系：
- 若 \(x=y\) ，则认为 \(x\) 与 \(y\) 相等。
- 否则，找到最小的正整数 \(i\) 使得 \(v_{p_i}(x)\neq v_{p_i}(y)\)，若 \(v_{p_i}(x)<v_{p_i}(y)\) 则认为 \(x\) 较小，否则认为 \(y\) 较小。
现在给出两个长度分别为 \(n,m\) 的正整数序列 \(a,b\) ，求将所有 \(a_i\times b_j\) 按上述规则从小到大排列后第 \(k\) 个数。
\(n,m\leq 10^5, 2\leq a_i,b_i\leq 10^6,1\leq k\leq n\times m\)
题解
记 \(V\) 为值域大小，下述 “\(<\)” 均表示题目中定义的小于关系。
首先，考虑对于两个整数 \(x,y\) ，如何尽快比较他们的大小。由于值域不大，我们可以通过预处理筛出每个正整数的最小质因子，来做到 \(O(\log V)\) 的分解质因数，这样就可以在 \(O(\log V)\) 的时间内比较值域内任意两个数大小（值域内任意两个数的积是类似的）。
题目所求是第 \(k\) 大，所以自然想到二分。假如已经确定 \(L<ans<R\) （ \(ans\) 为答案），那么如何表示出 \(ans\) 的可能取值呢？尝试枚举 \(i\)，寻找哪些 \(j\) 满足 \(L<a_i\times b_j<R\) 。这时候，可以发现一个关键的性质：如果有 \(a<b,c<d\)，那么就有 \(ac<bd\)（这是因为对于任意质数 \(p\)，\(v_p(ac)=v_p(a)+v_p(c),v_p(bd)=v_p(b)+v_p(d)\) ）。
所以，我们可以先对 \(a,b\) 两个序列分别按照题目规则排序。这样，对于固定的 \(i\)，满足 \(L<a_i\times b_j<R\) 的 \(j\) 一定是一段连续的下标区间 \([lb_i,rb_i]\) 。而且如果 \(i<j\) ，那么 \(lb_i\geq lb_j,rb_i\geq rb_j\)（这里的大小是通常实数上的大小关系）。这样，就可以通过双指针加上 \(O(\log V)\) 的大小比较，\(O(n\log V)\) 的时间内找出每个 \(i\) 的 \(lb_i,rb_i\)。
接下来，我们要选取二分的检验值。像通常一样取区间中点显然不好办到，但是我们可以在所有 \(\sum_{i=1}^n{rb_i-lb_i+1}\) 个可能的乘积中随机找一个。因为在区间 \([l,r]\) 内随机一个值，期望为 \(\frac{l+r}{2}\) ，所以区间长度也会期望变成原来的一半，那么二分的期望时间复杂度就可以保证。这样，我们每次在可能的乘积中随机一个，然后通过双指针处理出它对应的排名区间（因为可能有相同的数），如果可以是第 \(k\) 个，就得到答案，否则更新 \(L,R\) ，期望二分次数是 \(O(\log(nm))\)。
总复杂度 \(O((n+m)\log(nm)\log V)\) （其实二分部分和排序部分的复杂度是相当的）。