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

万能欧几里得算法

基本描述

对于一条直线 \(\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\) 分别为遇到横竖线的操作序列。

  • 若 \(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)\) 即可。
  • 否则,我们需要交换 \(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。考虑还需解决的问题: \(-r-1\) \(\not\in [0,p-1]\) 特殊处理操作序列没有 U 的情况,否则将原操作序列第一个 U 和其之前的 R 拿出来特殊处理。新直线变为 \(\dfrac{qx+(q-r-1\bmod p)}p\)。 原问题操作序列结尾是 R,而地位反转后新问题结尾一定是原问题的 U 操作。 仅剩若干个 R 操作未完成,递归结束后添上 \(n-\lfloor\dfrac{q\times cntu-r-1}{p}\rfloor(cntu=\lfloor\dfrac{pn+r}{q}\rfloor)\) 个 R 操作即可。
  • \(-r-1\) \(\not\in [0,p-1]\)
    特殊处理操作序列没有 U 的情况,否则将原操作序列第一个 U 和其之前的 R 拿出来特殊处理。新直线变为 \(\dfrac{qx+(q-r-1\bmod p)}p\)。
  • 原问题操作序列结尾是 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));
}

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

不愧其万能之称。

————————

万能欧几里得算法

基本描述

对于一条直线 \(\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\) 分别为遇到横竖线的操作序列。

  • 若 \(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)\) 即可。
  • 否则,我们需要交换 \(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。考虑还需解决的问题: \(-r-1\) \(\not\in [0,p-1]\) 特殊处理操作序列没有 U 的情况,否则将原操作序列第一个 U 和其之前的 R 拿出来特殊处理。新直线变为 \(\dfrac{qx+(q-r-1\bmod p)}p\)。 原问题操作序列结尾是 R,而地位反转后新问题结尾一定是原问题的 U 操作。 仅剩若干个 R 操作未完成,递归结束后添上 \(n-\lfloor\dfrac{q\times cntu-r-1}{p}\rfloor(cntu=\lfloor\dfrac{pn+r}{q}\rfloor)\) 个 R 操作即可。
  • \(-r-1\) \(\not\in [0,p-1]\)
    特殊处理操作序列没有 U 的情况,否则将原操作序列第一个 U 和其之前的 R 拿出来特殊处理。新直线变为 \(\dfrac{qx+(q-r-1\bmod p)}p\)。
  • 原问题操作序列结尾是 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));
}

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

不愧其万能之称。