万能欧几里得算法

2024-01-30

2.6k 词

问题描述

给出一个幺半群 $(S, \cdot)$ 和元素 $u, r \in S$ ，以及一条直线 $y = \frac{a x + b}{c}$ 。
画出平面中所有坐标为正整数的横线和竖线，维护一个 $f$ ，初值为单位元 $e$ 。
从原点出发，先向 $y$ 轴正方向走直到到达直线与 $y$ 的交点，然后沿直线走一直走到与 $x = n$ 的交点为止。
每当经过一条横线时，执行 $f \gets fu$ ，经过一条竖线时执行 $f \gets fr$ 。特别地，在 $y$ 轴上行走时不考虑竖线，同时经过横线和竖线时先执行前者。
求最终的 $f$ 。记为 $\mathrm{euclid}(a, b, c, n, u, r)$ 。
其中 $a, b \ge 0, n, c > 0$ 。

万能欧几里得算法

分情况考虑。

设 $m = \lfloor\frac{an + b}{c}\rfloor$ 。

当 $m = 0$ 时，答案为 $r ^ n$ 。

当 $b \ge c$ ，即 $\frac{b}{c} \ge 1$ 时，在 $y$ 轴上行走的贡献为 $u ^ {\lfloor\frac{b}{c}\rfloor}$ ，而剩余部分相当于 $y = \frac{ax + (b \bmod c)}{c}$ 时的答案，因此答案为 $u ^ {\lfloor\frac{b}{c}\rfloor} \mathrm{euclid}(a, b \bmod c, c, n, u, r)$ 。

（图片来源于同学课件）

当 $a \ge c$ ，即 $\frac{a}{c} \ge 1$ 时，任意相邻两个 $r$ 之间至少有一个 $u$ 的贡献，考虑将这个贡献算到 $r$ 上，也就是 $r \gets ur$ 。
此时我们需要改变直线使得相邻两个 $r$ 之间都恰好减少一个 $u$ 的贡献。
可以发现相邻两个 $r$ 之间 $u$ 的贡献的数量是由两个 $r$ 的 $y$ 坐标的差值决定的，因此相当于时相邻两个 $r$ 的 $y$ 坐标的差值都减少 $1$ ，相当于斜率减 $1$ 。因此直线变为 $y = \frac{(a - c)x + b}{c}$ 。
重复这个过程即可得到答案为 $\mathrm{euclid}(a \bmod c, b, c, n, u, u ^ {\lfloor\frac{a}{c}\rfloor} r)$ 。

剩余的最后一种情况就是 $a < c$ 且 $b < c$ 。考虑将平面沿 $y = x$ 对称。对于同时遇到 $u, r$ 的问题，可以将直线向右平移 $\frac{1}{c}$ 。

可以把贡献拆成三部分，第一次 $u$ 及以前，中间部分和最后一次 $u$ 之后。
第一部分答案为 $r ^ {\lfloor\frac{c - b - 1}{a}\rfloor} u$ 。
第三部分考虑原直线最后一个 $u$ 的位置为 $y = \lfloor\frac{an + b}{c}\rfloor = m$ ，对称后即为 $x = m$ ，此时 $y = \frac{c m - b - 1}{a}$ ，因此有 $n - \lfloor\frac{c m - b - 1}{a}\rfloor$ 个 $r$ 的贡献，答案为 $r ^ {n - \lfloor\frac{c m - b - 1}{a}\rfloor}$ 。
对于第二部分，考虑截掉前两部分，也就是保留 $x = m$ 以前（包含）的部分，然后将直线左移 $1$ ，下移 $\lfloor\frac{c - b - 1}{a}\rfloor$ 。

因此这部分答案为 $\mathrm{euclid}(c, (c - b - 1) \bmod a, a, m - 1, r, u)$ 。