问题本质

从 $n^2$ 个分数 $\frac{a_i}{b_j}$ 中找出第 $c_j$ 小的分数（化简后），不能直接生成所有分数。

核心思路：二分答案

关键观察

• 分数值范围有限：$[\frac{\min A}{\max B}, \frac{\max A}{\min B}]$
• 对于候选值 $x$，可在 $O(n)$ 时间内计算有多少分数 $\leq x$

算法步骤

1. 预处理：对数组 $A$ 和 $B$ 排序

2. 二分搜索：

   • 对每个查询 $c_j$，二分搜索第 $c_j$ 个分数值
   • 比较分数时使用 $a_i \times b_k \leq x \times b_j \times b_k$ 避免浮点数

3. 计数函数：

   long long count_leq(double x) {
       long long cnt = 0;
       // 对每个 b_j，找到最大的 a_i 满足 a_i/b_j <= x
       // 使用双指针优化
   }
   

4. 分数化简：找到分数后，用 GCD 化简输出

复杂度

• 预处理：$O(n \log n)$
• 每个查询：$O(n \log M)$，其中 $M$ 是值域
• 满足 $n \cdot q \leq 10^5$ 的限制

实现要点

• 使用整数比较避免精度问题
• 注意处理分数相等的情况
• 输出最简分数形式