题解：CF1418F Equal Product

· · 题解

水题。

如果枚举 $x_1$ 和 $y_1$，那么只需要枚举 $p|x_1,q|y_1(q>p)$ 取出 $(\dfrac{qx_1}{p},\dfrac{py_1}{q})$ 作为 $(x_2,y_2)$，当然需要判第一个超不超过 $n$。 于是枚举 $x_1$ 和 $p$，容易写出 $q\in [q_l,q_r],y\in[y_l,y_r],q|y$ 的限制，我们可以使用整除分块计算 $\sum_{i=L}^{R} \lfloor\dfrac{Q}{i}\rfloor-\lfloor\dfrac{P}{i}\rfloor$ 来判定存在性。一旦存在，我们就可以二分第一个 $y$ 使此式不为 $0$。 前面枚举 $O(n\log n)$，二分也是 $O(n\log n)$，复杂度 $O(n\sqrt{n}\log n)$。 <https://codeforces.com/contest/1418/submission/345123051>。