万能欧几里得

这个目前网上好像没有详细的教程，我来造福社会吧。

为了方便本文的叙述，做一个不严谨的规定。在本文中一个$01$串可以对应一些信息，并且这些信息是支持合并的，即如果用$g(S)$表示$01$串$S$对应的信息，那么可以用$g(S)$和$g(T)$计算出$g(S+T)$。因此我们不妨类比字符串，将这类信息的合并看作是加法。同样的，这类信息与数字的乘法代表连续的合并。

万能欧几里得可以解决基本所有的类欧几里得问题，而且不同的问题不需要重新推式子，只需要稍作修改即可。

首先来形式化的说明一下万能欧几里得能解决的问题：

给定$p,q,r,l$以及$g{(}^{\prime }{0}^{\prime })$和$g{(}^{\prime }{1}^{\prime })$，并给出一种信息合并的方式满足$g(S)+g(T)=g(S+T)$。从左至右考虑函数$y=\frac{px+r}{q}$在$(0,l]$内的直线并维护一个$01$字符串$S$，每当和$x=c$（$c$是整数）相交时在$S$的末尾添加${}^{\prime }{0}^{\prime }$，每当和$y=c$（$c$是整数）相交时在$S$的末尾添加${}^{\prime }{1}^{\prime }$，当经过整点时先添加${}^{\prime }{1}^{\prime }$后添加${}^{\prime }{0}^{\prime }$。求$01$串$S$所对应的信息。

可以发现类欧几里得问题都可以转化为上述问题。举个例子，如果我们要求：

$$\sum _{i=0}^{l}i\lfloor \frac{pi+r}{q}\rfloor$$

那么从结果上来讲我们只需要知道每个串对应的$\sum i\lfloor \frac{pi+r}{q}\rfloor$，考虑对两个串进行合并，那么对于后面的串来讲$\sum i\lfloor \frac{pi+r}{q}\rfloor$就变成了$\sum (i+x)(\lfloor \frac{pi+r}{q}\rfloor +y)$，其中$x$，$y$分别是前面的串中$i$和$\lfloor \frac{pi+r}{q}\rfloor$最终的值。那么显然为了合并$x$和$y$也是需要维护的。

进一步考虑$\sum (i+x)(\lfloor \frac{pi+r}{q}\rfloor +y)=(\sum i\lfloor \frac{pi+r}{q}\rfloor )+(x\sum \lfloor \frac{pi+r}{q}\rfloor )+(y\sum i)+(xy\sum 1)$，考虑到$\sum i$和$\sum 1$都可以由后面的串的$x$直接得到因此无需维护，只需要再对$\sum \lfloor \frac{pi+r}{q}\rfloor$进行维护即可。维护的计算方式稍加推导即可得知。

我们将解决上述问题的方法表示为$f(p,q,r,l,s_0,s_1)$（其中$s_0$、$s_1$分别表示$g{(}^{\prime }{0}^{\prime })$、$g{(}^{\prime }{1}^{\prime })$），考虑如何递归至更小的规模：

首先可以发现，我们将$r$对$q$取余是没有关系的（因为$S$不会改变），于是可以保证$r<q$。

接着，如果$p<q$考虑如何转化为$p\ge q$。发现这或许可以通过将坐标系的横纵轴翻转解决。我们设$k=\lfloor \frac{pl+r}{q}\rfloor$，那么可以考虑先处理好值域在$(1,k]$之间的部分。如果$k=0$，那么不会经过$y=c$，我们直接返回$s_0\ast l$。否则我们将坐标轴反转并平移，可以使之前的问题等价于函数$y=\frac{qx+(q-r)}{p}$在$(0,k-1]$之间的部分，此时我们需要将$s_0$与$s_1$互换。不过这里有一个问题是互换了$s_0$和$s_1$以后，如果经过了整点那么实际的顺序会与我们规定的相反，为了解决这个问题，我们将函数整体向下平移$\frac{1}{p}$，即变成$y=\frac{qx+(q-r-1)}{p}$，那么原来的经过整点就变成了先与$x=c$相交的情况，和我们期望的一致，并且对其它的经过方式都不会产生结果上的变化。当然这会对头尾的需要单独处理的一小部分产生一些影响，接下来会说明这个问题。现在我们可以递归到$f(q,p,q-r-1,s_1,s_0)$。

接下来还需要处理首尾的问题。先考虑开头，由于我们已经处理了值域在$1$之后的，那么与$y=c$相交的情况只会出现一次，于是我们统计与$x=c$相交的次数，那么就是函数与$y=1$相交的点的横坐标的下取整即$\lfloor \frac{q-r}{p}\rfloor$。不过需要特别注意的是当$\frac{q-r}{p}$为整数时，我们经过了$(1,\frac{q-r}{p})$这个整点，而由于我们之前将递归的函数下移了$\frac{1}{p}$，因此递归的部分实际上会将与$x=\frac{q-r}{p}$相交的情况包含，因此我们在开头需要计算的与$x=c$相交的次数只有$\lfloor \frac{q-r-1}{p}\rfloor$次，之后再与$y=1$相交。即，在开头需要额外添加的信息是$s_0\ast \lfloor \frac{q-r-1}{p}\rfloor +s_1$。

尾部的问题也是类似的。由于函数值的整数部分不会再增加，于是只有与$x=c$相交的情况。计算可得与$y=k$相交的点横坐标为$\frac{kq-r}{p}$，由于递归下去的函数平移了$\frac{1}{p}$因此我们实际上只处理到了$\frac{kq-r-1}{p}$，于是我们在末尾加上$s_0\ast (l-\lfloor \frac{kq-r-1}{p}\rfloor )$即可。

于是我们可以保证$p\ge q$，考虑怎么解决这一部分。

我们设$k=\lfloor \frac{p}{q}\rfloor$，那么原函数可以表示为$y=kx+\frac{(pmodq)x+r}{q}$，将其与函数$y=\frac{(pmodq)x+r}{q}$相比，相当于在每次经过$x=c$之前额外经过$k$次$y=c$。于是我们可以递归至$f(pmodq,q,r,l,s_1\ast k+s_0,s_1)$。

综上所述，我们完整的解决了万能欧几里得问题。为了使思路更加清晰，我们用伪代码的形式重新整理一遍之前的方法。

$f(p,q,r,l,s_0,s_1)$ $r=rmodq$ $\text{if}p<q\text{then}$ $k=\lfloor \frac{pl+r}{q}\rfloor$ $\text{if}k=0\text{then}$ $\text{return}{s}_0\ast l$ $\text{return}{s}_0\ast \lfloor \frac{q-r-1}{p}\rfloor +s_1+f(q,p,q-r-1,k-1,s_1,s_0)+s_0\ast (l-\lfloor \frac{kq-r-1}{p}\rfloor )$ $\text{else}$ $k=\lfloor \frac{p}{q}\rfloor$ $\text{return}f(pmodq,q,r,l,s_1\ast k+s_0,s_1)$

如果将维护信息的加法和乘法的复杂度看作$O(1)$，那么万能欧几里得的复杂度与欧几里得算法的分析相似，为$O(\log n)$。值得注意的是通常为了方便乘法可以用倍增进行快速乘，不过如果分析系数与乘数的关系可以得到更快的方法。

$P.S.$用平移$\frac{1}{p}$的方式处理特殊要求的方法是嘿嘿嘿同学告诉我的，嘿嘿嘿太强了。