题解：AT_agc063_f [AGC063F] Simultaneous Floor

把有序数对看成坐标，扔到平面直角坐标系上研究。下面记点 $A(a_1,a_2),B(b_1,b_2)$。不加说明时，我们均指第一象限。记值域为 $V$。

发现点 $P(x,y)$ 可以变成形如 $(i,\lfloor\dfrac{y}{x}i\rfloor),(\lfloor\dfrac {x}{y}i\rfloor,i),i\in\mathbb Z$ 的点。不过还是有向下取整，不好描述。

那么倒过来看，对于 $Q(p,q)$，能够到达它的 $P$ 的集合是什么。

设直线 $OP:y=kx$，如果 $P$ 能到达 $Q$，则 $OP$ 必须穿过以 $Q$ 为左下角、边长为 $1$ 的正方形，穿过是指 $OP$ 在正方形内的部分的长度 $>0$。

设 $Q_u(p,q+1),Q_r(p+1,q)$，则只要 $OP$ 在 $\angle Q_rOQ_u$ 内部（不包括 $OQ_u,OQ_r$），其就会穿过这个正方形。

那么就有 $k\in(k_{OQ_r},k_{OQ_u})$，即能够到达 $Q(p,q)$ 的 $P\in\{(x,y)|\dfrac{q}{p+1}<\dfrac y x<\dfrac{q+1}p\}$。

设 $l_1=\dfrac{b_2}{b_1+1},r_1=\dfrac{b_2+1}{b_1}$，我们就可以算出经过 $\le 1$ 次操作到达 $B$ 的点的集合为 $S_1=\{(x,y)|l_1<\dfrac y x<r_1\}$。

同理，设 $l_2=\min\{\dfrac y{x+1}|(x,y)\in S_1\},r_2=\max\{\dfrac{y+1}x|(x,y)\in S_1\}$，则经过 $\le 2$ 次操作到达 $B$ 的点的集合为 $S_2=\{(x,y)|l_2<\dfrac y x<r_2\}$。

更一般地，对于 $t\ge 2$，设 $l_t=\min\{\dfrac y{x+1}|(x,y)\in S_{t-1}\},r_t=\max\{\dfrac{y+1}x|(x,y)\in S_{t-1}\}$，则经过 $\le t$ 次操作到达 $B$ 的点的集合为 $S_t=\{(x,y)|l_t<\dfrac y x<r_t\}$。

先来研究已知 $l_{t-1},r_{t-1}$ 如何求 $l_t,r_t$。下面只讨论 $l_t$，$r_t$ 是类似的。

问题相当于求最小的 $\dfrac{y}{x+1}$，满足 $l_{t-1}<\dfrac{y}{x}<r_{t-1}$。考虑到 $\dfrac{y}{x+1}=\dfrac{1}{\frac{x}{y}+\frac{1}{y}}$，即我们要 $y$ 尽量小 $\dfrac{x}{y}$ 尽量大。在 $y$ 最小的同时取 $x$ 最大即可，可以用反证法和一些缩放证明。

同理，求 $r_t$ 时找满足 $x$ 最小的最大 $y$ 即可。

找到这样的 $x,y$ 可以在 SBT 上二分实现。

接下来就是要求第一次满足 $A\in S_t$ 的 $t$。打表发现 $l_t,r_t$ 在迭代若干轮之后就不变了，所以可以暴力求每一轮的 $l_t,r_t$ 是多少。考虑到 $l,r$ 在 SBT 上移动的过程，得到 $x=1$ 或 $y=1$ 后就不会变了，所以迭代次数是 $O(\log V)$ 的。

注意有点在坐标轴、$y=x$ 上以及不在 $y=x$ 同一侧的时候判无解。可以用关于 $y=x$ 对称简化讨论。

总的复杂度是 $O(T\log^2 V)$。