这个目前网上好像没有详细的教程，我来造福社会吧。
为了方便本文的叙述，做一个不严谨的规定。我们将函数与函数间的复合运算表示为乘法。即，如果\(h(x)=g(f(x))\)，那么可以表示为\(h=fg\)（这里的乘法是有顺序的）。同理，连续的复合可以表示成乘方。我们将函数的单位元记作\(\epsilon\)。
万能欧几里得可以解决基本所有的类欧几里得问题，而且不同的问题不需要重新推式子，只需要稍作修改即可。缺点是常数比较大。
首先来形式化的说明一下万能欧几里得能解决的问题：
给定\(p,q,r,l,t\)，从左至右考虑函数\(y=\frac{px+r}{q}\)在\((0,l]\)内的直线并维护一个\(01\)字符串，每当和\(x=c\)（\(c\)是常数）相交时在\(s\)的末尾添加\(‘0‘\)，每当和\(y=c\)（\(c\)是常数）相交时在\(s\)的末尾添加\(‘1‘\)，当经过整点时添加的先后顺序则由参数\(t\)来决定，当\(t=0\)时先添加\(‘1‘\)后添加\(‘0‘\)，\(t=1\)则相反。
考虑一种数据类型以及对应于这种数据类型的两个函数\(s_0\)和\(s_1\)，从单位元\(\epsilon\)开始，并从左至右遍历字符串\(s\)，每当遇到\(‘0‘\)则将当前值右乘以\(s_0\)，每当遇到\(‘1‘\)则将当前值右乘以\(s_1\)，求最终的结果。万能欧几里得对函数\(s_0,s_1\)的唯一要求是满足结合律。
可以发现类欧几里得问题都可以转化为上述问题。举个例子，如果我们要求：
\[\sum_{i=0}^li\lfloor\frac{pi+r}{q}\rfloor\]
那么可以看作是维护三元组\((i,\lfloor\frac{pi+r}{q}\rfloor,i\lfloor\frac{pi+r}{q}\rfloor,ans)\)，那么每遇到一个\(‘0‘\)就是将\(i\)增加\(1\)，将\(i\lfloor\frac{pi+r}{q}\rfloor\)增加\(\lfloor\frac{pi+r}{q}\rfloor\)，并将\(ans\)增加\(i\lfloor\frac{pi+r}{q}\rfloor\)，每遇到一个\(’1’\)就是将\(\lfloor\frac{pi+r}{q}\rfloor\)增加\(1\)，将\(i\lfloor\frac{pi+r}{q}\rfloor\)增加\(i\)。可以将贡献转化为系数并用矩阵表示一个函数。当然也可以根据特殊性进行进一步简化（略为繁琐的转化也是万欧比较慢的原因）。
我们将解决上述问题的方法表示为\(f(p,q,r,l,s_0,s_1,t)\)，考虑如何递归至更小的规模：
首先可以发现，我们将\(r\)对\(q\)取余是没有关系的，于是可以保证\(r<q\)。
接着，如果\(p<q\)考虑如何转化为\(p\geq q\)。发现这或许可以通过将坐标系的横纵轴翻转解决。我们设\(k=\lfloor\frac{pl+r}{q}\rfloor\)，那么可以考虑先处理好值域在\((1,k]\)之间的部分。如果\(k=0\)，那么不会经过\(y=c\)，我们直接返回\(s_0^l\)。否则我们将坐标轴反转并平移，可以使之前的问题等价于函数\(y=\frac{qx+(q-r)}{p}\)在\((0,k-1]\)之间的部分，此时我们需要将\(s_0\)与\(s_1\)互换，并将参数\(t\)反转。即递归至\(f(q,p,q-r,k-1,s_1,s_0,t\oplus 1)\)。
接下来还需要处理首尾的问题。先考虑开头，由于我们已经处理了值域在\(1\)之后的，那么与\(y=c\)相交的情况只会出现一次，于是我们统计与\(x=c\)相交的次数，那么就是函数与\(y=1\)相交的点的横坐标的下取整即\(\lfloor\frac{q-r}{p}\rfloor\)。此处需要进行一个特判，如果\(\frac{q-r}{p}\)为整数，那么我们就经过了一个整点，此时如果\(t=0\)，我们需要看作先与\(y=1\)相交再与\(x=c\)相交，也就是乘以\(s_0^{\lfloor\frac{q-r}{p}\rfloor-1}s_1s_0\)。其余情况下所有的与\(x=c\)相交都在与\(y=1\)相交之前，也就是乘以\(s_0^{\lfloor\frac{q-r}{p}\rfloor}s_1\)。
尾部的问题就简单一些。由于函数值的整数部分不会再增加，于是只有与\(x=c\)相交的情况。计算可得与\(y=k\)相交的点横坐标为\(\frac{kq-r}{p}\)，于是我们乘以\(s_0^{l-\lfloor\frac{kq-r}{p}\rfloor}\)即可。
于是我们可以保证\(p\geq q\)，考虑怎么解决这一部分。
首先假如\(q|p\)，那么原函数可以表示为\(y=kx+\frac{r}{q}\)的形式，其中\(k=\frac{p}{q}\)且为整数。对此进行特判，假如\(r=0\)，那么当横坐标为整数时纵坐标也是整数，即经过整点，此时如果\(t=1\)，那么答案就是\((s_1^{k-1}s_0s_1)^l\)，其余情况下答案都是\((s_1^ks_0)^l\)。
考虑剩下来的情况。我们设\(k=\lfloor\frac{p}{q}\rfloor\)，那么原函数可以表示为\(y=kx+\frac{(p\ \bmod\ q)x+r}{q}\)，将其与函数\(y=\frac{(p\ \bmod\ q)x+r}{q}\)相比，相当于在每次经过\(x=c\)之前额外经过\(k\)次\(y=c\)，并且由于\(p\bmod q\)不为\(0\)，因此如果原函数交于整点新函数也必定交于整点，可以不考虑这方面的特判。于是我们可以递归至\(f(p\bmod q,q,r,l,s_1^ks_0,s_1,t)\)。
综上所述，我们完整的解决了万能欧几里得问题。为了使思路更加清晰，我们用伪代码的形式重新整理一遍之前的方法。
\(f(p,q,r,l,s_0,s_1,t)\)
\(\ \ \ \ r=r\bmod q\)
\(\ \ \ \ \text{if}\ p<q\ \text{then}\)
\(\ \ \ \ \ \ \ \ k=\lfloor\frac{pl+r}{q}\rfloor\)
\(\ \ \ \ \ \ \ \ \text{if}\ k=0\ \text{then}\)
\(\ \ \ \ \ \ \ \ \ \ \ \ \text{return}\ s_0^l\)
\(\ \ \ \ \ \ \ \ \text{if}\ t=0\ \text{and}\ (q-r)\bmod p=0\ \text{then}\)
\(\ \ \ \ \ \ \ \ \ \ \ \ \text{return}\ s_0^{\lfloor\frac{q-r}{p}\rfloor-1}s_1s_0f(q,p,q-r,k-1,s_1,s_0,t\oplus 1)s_0^{l-\lfloor\frac{kq-r}{p}\rfloor}\)
\(\ \ \ \ \ \ \ \ \text{else}\)
\(\ \ \ \ \ \ \ \ \ \ \ \ \text{return}\ s_0^{\lfloor\frac{q-r}{p}\rfloor}s_1f(q,p,q-r,k-1,s_1,s_0,t\oplus 1)s_0^{l-\lfloor\frac{kq-r}{p}\rfloor}\)
\(\ \ \ \ \text{else}\)
\(\ \ \ \ \ \ \ \ \text{if}\ p\bmod q=0\ \text{then}\)
\(\ \ \ \ \ \ \ \ \ \ \ \ \text{if}\ t=1\ \text{and}\ r=0\ \text{then}\)
\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{return}\ (s_1^{k-1}s_0s_1)^l\)
\(\ \ \ \ \ \ \ \ \ \ \ \ \text{else}\)
\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{return}\ (s_1^{k}s_0)^l\)
\(\ \ \ \ \ \ \ \ \text{else}\)
\(\ \ \ \ \ \ \ \ \ \ \ \ \text{return}\ f(p\bmod q,q,r,l,s_1^ks_0,s_1,t)\)
如果将函数的乘法和乘方的复杂度看作\(O(1)\)，那么万能欧几里得的复杂度与欧几里得算法的分析相似，为\(O(\log n)\)。
原文：https://www.cnblogs.com/Mr-Spade/p/10370259.html