万能欧几里得算法学习笔记

万能欧几里得算法

基本描述

对于一条直线 /(/dfrac {px+r}{q}/)，满足 /(p>0,q>0,r/in[0,q-1]/)，求解有关 /(/lfloor/dfrac {px+r}{q}/rfloor,x/) 的一些函数。
考虑在坐标系上考虑这条直线，从 /((0,0)/) 开始走。

定义当直线穿过一条形如 /(y=h(h/in/Z)/) 的横线（下文会称其为横线）时进行一次 U 操作（往上走一格，对一些变量进行一定修改）。
定义当直线穿过一条形如 /(x=k(k/in /Z)/) 的竖线（下文会称其为竖线）时进行一次 R 操作（往右走一格，对一些变量进行一定修改）。
特别的，规定直线遇到整点时先 U 后 R。

我们要求 U 和 R 操作有结合律。

算法流程

考虑将问题类似欧几里得算法的迭代过程，递归到子问题中。

/(/text{solve}(p,q,r,n,U,R)/) 表示处理 /(y=/dfrac{px+r}{q},x/in(0,n]/) 这一条线段，/(U,R/) 分别为遇到横竖线的操作序列。

1. 若 /(p/geq q/)，我们尝试将问题递归到规模为 /(p/bmod q/) 的子问题。

   观察到 /(p/geq q/) 时，每一个 R 操作前都会有至少 /(/lfloor/dfrac p q/rfloor/) 个 U 操作，将其与 R 缩成一个操作，那么考虑新局面下 /(x/) 时的 U 操作个数：
   /(/lfloor/dfrac {px+r}{q}/rfloor-x/lfloor/dfrac p q/rfloor=/lfloor/dfrac {px+r}{q}/rfloor-x/dfrac{p-(p/bmod q)}{q}//=/lfloor/dfrac {px+r-xp+x(p/bmod q)}{q}/rfloor=/lfloor/dfrac{(p/bmod q)x+r}{q}/rfloor/)

   递归到子问题 /(/text{solve}(p/bmod q,q,r,n,U,U^{p/q}R)/) 即可。

2. 否则，我们需要交换 /(p,q/) 的地位，进入第一部分的迭代。

   交换 /(p,q/) 地位类似于翻转坐标系，我们考虑第 /(a/) 个 R 前有 /(/lfloor/dfrac{pa+r}{q}/rfloor/) 个 U。
   考虑第 /(b/) 个 U 前有多少个 R，设第 /(a/) 个 R 在第 /(b/) 个 U 前。

   /[b>/lfloor/frac{pa+r}{q}/rfloor,b>/frac{pa+r}{q}//a</frac{qb-r}{p},a/leq/lfloor/frac{qb-r-1}{p}/rfloor
   /]

   第 /(b/) 个 U 前有 /(/lfloor/dfrac{qb-r-1}{p}/rfloor/) 个 R。考虑还需解决的问题：

   1. /(-r-1/) /(/not/in [0,p-1]/)

      特殊处理操作序列没有 U 的情况，否则将原操作序列第一个 U 和其之前的 R 拿出来特殊处理。新直线变为 /(/dfrac{qx+(q-r-1/bmod p)}p/)。

   2. 原问题操作序列结尾是 R，而地位反转后新问题结尾一定是原问题的 U 操作。

      仅剩若干个 R 操作未完成，递归结束后添上 /(n-/lfloor/dfrac{q/times cntu-r-1}{p}/rfloor(cntu=/lfloor/dfrac{pn+r}{q}/rfloor)/) 个 R 操作即可。

若合并两个操作序列的复杂度为 /(O(c)/)，那么万能欧几里得算法的复杂度为 /(O(c/log/max(p,q))/)。
复杂度证明类似欧几里得算法。

应用场景

对于这样的题目只要想清楚怎么维护操作序列的合并即可，迭代过程的代码都不需要修改！

ll div(ll a,ll b,ll c,ll d){return ((lll)a*b+c)/d;}
node solve(ll p,ll q,ll r,ll n,node U,node R){
    if(!n)return o;
    if(p>=q)return solve(p%q,q,r,n,U,power(U,p/q)+R);
    ll m=div(p,n,r,q);
    if(!m)return power(R,n);
    return (power(R,(q-r-1)/p)+U)+solve(q,p,(q-r-1)%p,m-1,R,U)+power(R,n-div(q,m,-r-1,p));
}

而能合并的操作序列也很广泛，仅要求是线性变换就可以了！

不愧其万能之称。