万能欧几里得

​​#6440. 万能欧几里得​​

计算

• 万能欧几里得算法：我们做直线 从 开始走，维护一个三元组 ，碰到上边界则将 左乘上 ，碰到左边界就把 右乘上 ，并更新答案
• 发现这个操作可以构成一个序列，形如
  万能欧几里得算法可以将这个序列合并，压缩使得我们能快速得到答案
  令 ，其中 表示我们的一段序列
• 若，则发现一个 前面一定有 个
  于是我们可以令 ，实现了序列的压缩
• 若，我们可以通过变换使其变为 的情况，这个变换就叫做坐标旋转
  我们考虑求出 的反函数，即为解一个方程
  
  那么若实现坐标翻转，某一个特定的 可以前可以有
  个 ，对比前面一个特定的 前有 ，那么新的直线可以写作
  注意分母无论减去多少个分子都不会影响操作序列
  然后这里的定义域要映射成值域， 时不能取满所以我们单独计算，所以新的定义域变成了 ，同时定义域后方还有一些点没有算到，同样单独计算
  然后我们就可以递归到 来计算
  ​​
• 既然它是万能的，那么我们可以顺手切掉一道​​【模板】类欧几里得算法​​ 维护一个 5 元组 合并的时候拆项讨论就做完了
  比类欧几里得好写到哪里去了，不过脑子够笨还是码了好久
  ​​