类欧几里得的一个方法
最近学到了一个牛逼的类欧推导方式，优点是好想好写缺点是常数大...
考虑把那条 (frac{ax+b}{c}) 直线画出来，这条直线碰到一次直线 (x = a) 执行一次 (A) 操作，碰到一次直线 (y = b) 执行一次 (B) 操作，形成一个操作序列，这个算法的要求是这个序列可以快速合并（我遇到的题都满足）。
考虑函数 solve(p, q, r, n, A, B) 表示一共有 (n) 个 (B) 操作，第 (i) 个 (B) 操作前面共有 (lfloor frac{pi+r}{q}
floor) 个 (A) 操作，这样一个序列的答案。
首先 B = A * (p / q) + B, p = p % q, r = r % q，(p) 的部分正确性显然， (r) 的部分等一下再说。
考虑第 (x) 个 (A) 和在它之后的第 (y) 个 (B)：
[egin{aligned}
x &le lfloor frac{py+r}{q}
floor\
qx &le py + r\
frac{qx-r}{p} &le y\
lceil frac{qx-r}{p}
ceil &le y\
lfloor frac{qx-r+p-1}{p}
floor &le y
end{aligned}
]
于是第 (i) 个 (A) 前面共有 (lfloor frac{qi-r-1}{p} floor) 个 (B)。
这个时候 (-r - 1) 是负数不太好搞，我们把它加上 (q)，然后把第一个 (A) 拿出来单独处理（这是之前 r = r % q 的原因），注意最后的 (B) 也要特殊处理。
代码：
Solver euclid(LL p, LL q, LL r, LL l, const Solver &a, const Solver &b) {
r %= q;
if (!l) {
return Solver();
}
if (p >= q) {
return euclid(p % q, q, r, l, a, a * (p / q) + b);
}
LL m = (p * l + r) / q;
if (!m) {
return b * l;
}
LL cnt = l - (q * m - r - 1) / p;
return b * ((q - r - 1) / p) + a + euclid(q, p, q - r - 1, m - 1, b, a) + b * cnt;
}