取自 CTT 2022 Day4 T3 (或许是2021?)
考虑用以下方法描述一个万能欧几里得问题:
有一条端点为 \((0,0)\rightarrow (A,B)\) 的有向线段 \(OP\),我们认为其两端都是空的。
其中 \(A,B\) 是自然数,且 \(\gcd(A,B)=1\)。(当 \(g=\gcd(A,B)\ne 1\) 时,可以先求 \(\frac{A}{g},\frac{B}{g}\) 的结果,然后将其复制 \(g\) 次)。
万能欧几里得问题要维护这样的一个过程:
一开始我们有一个空字符串 \(s\)。
考虑点从 \(O\) 移动到 \(P\) 的过程:
注意在 \(O,P\) 处不加入字符。容易发现在 \(\gcd(A,B)=1\) 时,不会出现同时经过 \(x,y\) 上的整点。
下图是 \(P=(3,5)\) 时的例子,此时的字符串为 \(\text{YXYYXY}\)。
在实际的应用中,我们用 \(\text{X,Y}\) 指代任何可拼接且满足结合律的操作(如矩阵)。
用四元组 \((A,B,\text{X},\text{Y})\) 描述这样的一个万能欧几里得问题,则可以如下递归求解:
容易发现递归的问题同样是合法的万能欧几里得问题。
设 \(l=\lfloor\frac{B}{A} \rfloor\),递归时需要处理 \(\text{Y}\cdot l\),这是一个快速幂操作,其复杂度为 \(\log l\)。
而 \(B\mod A=B-A\cdot l\leq \frac{1}{l+1} B\),所以所有快速幂的复杂度总和为 \(\log A+\log B\)。
考虑万能欧几里得的过程,容易发现其中只有两种操作:
如果我们用一个节点描述一个操作,就可以用二叉树的结构维护拼接操作。
对于快速幂,只需要对于节点进行可持久化。
而万能欧几里得所产生的二叉树至多只有 $\log $ 层,在这样的二叉树上查询的复杂度与线段树相同。