模型：对于一条直线 y=\frac{px+r}{q}，我们取其 x\in(0,M] 的部分，维护一个信息，从左往右，它每与一条平行于 x 轴的坐标轴相交，执行 U 操作，每与一条平行于 y 轴的坐标轴相交，执行 R 操作。求出经过所有操作之后的信息。如果与两个坐标轴同时相交，我们默认先执行 U 再执行 R。
更形式化一点的定义：有两种操作 U,R，我们交替执行两种操作，操作 R 执行恰好 M 次，且第 x 次 R 操作之前有恰好 \lfloor\frac{px+r}{q}\rfloor 次 U 操作，求出最后结果。
我们定义这个值为 F(p,q,r,M,U,R)。类似于求 \gcd 的辗转相除，我们用两个操作来在 O(\log M) 的时间复杂度内解决这个问题。这里默认操作的复合是 O(1) 的，且操作要满足结合律。
如果 p\geq q，那么两次 R 操作之间有 \lfloor\frac{p(x+1)+r}{q}\rfloor-\lfloor\frac{px+r}{q}\rfloor 次 U 操作，这个值显然至少是 \lfloor\frac{p}{q}\rfloor。我们考虑把这 \lfloor\frac{p}{q}\rfloor 次 U 和下一次 R 合并，也就是令 R'=U^{\lfloor\frac{p}{q}\rfloor}R，这时剩余的 U 恰好有 \lfloor\frac{(p\bmod q)(x+1)+r}{q}\rfloor-\lfloor\frac{(p\bmod q)x+r}{q}\rfloor 个，那么我们就得到了：
如果 p<q，我们希望将 p,q 地位交换。考虑求一下第 y 个 U 之前有多少 R 操作，列出不等式 y> \frac{px+r}{q}，也就是 x\leq \frac{qy-r-1}{p}。这个非常符合原问题的形式，但是唯一有小毛病的地方就是后面的 +r 变成了 -r-1，这个是负值。解决方法也很简单，将式子改成 \frac{q(y-1)+(q-r-1)}{p}，然后特殊处理第一段和最后一段 R 即可。得到的式子是：