前置知识

$\lfloor \frac{a}{b} \rfloor$ 表示 $a$ 除以 $b$ 向下取整的结果。

在一定情况下，我们希望将带有「向下取整」的不等式转化为不带有「向下取整」的不等式。方便起见，在下面列出其公式，其中 $a, b, c, d$ 均为整数：

$$ c \le \left \lfloor \frac{a}{b} \right \rfloor < d \iff bc \le a < bd $$

在转化的过程中，通过一些 $\pm 1$ 可以规避掉一些是否能够整除时的细节。

类欧几里得算法

主要用于求解 floor sum 问题及其变体。即给定 $n, a, b, c$ 的值，求下式的值：

$$ f(n, a, b, c) = \sum_{i = 0}^{n} \left \lfloor \frac{a i + b}{c} \right \rfloor $$

为了便于讨论，钦定 $a, b \in [0, c)$。对于 $a, b \notin [0, c)$ 的情况可以进行转化，具体方法如下：

$$ \begin{aligned} f(n, a, b, c) =& \sum_{i = 0}^{n} \left \lfloor \frac{a i + b}{c} \right \rfloor \\ =& \sum_{i = 0}^{n} \left \lfloor \frac{(\left \lfloor \frac{a}{c} \right \rfloor c + a \bmod c) i + \left \lfloor \frac{b}{c} \right \rfloor + b \bmod c}{c} \right \rfloor \\ =& \sum_{i = 0}^{n} \left \lfloor \frac{a}{c} \right \rfloor i + \left \lfloor \frac{b}{c} \right \rfloor + \left \lfloor \frac{(a \bmod c) i + b \bmod c}{c} \right \rfloor \\ =& \frac{n(n + 1)}{2} \left \lfloor \frac{a}{c} \right \rfloor + (n + 1) \left \lfloor \frac{b}{c} \right \rfloor + f(n, a \bmod c, b \bmod c, c) \end{aligned} $$

之后的算法流程中，均确保 $a, b \in [0, c)$。

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

$$ \begin{aligned} f(n, a, b, c) =& \sum_{i = 0}^{n} \left \lfloor \frac{a i + b}{c} \right \rfloor \\ =& \sum_{i = 0}^{n} \sum_{j = 0}^{\left \lfloor \frac{a i + b}{c} \right \rfloor - 1} 1 \\ =& \sum_{j = 0}^{m - 1} \sum_{i = 0}^{n} \left [j < \left \lfloor \frac{a i + b}{c} \right \rfloor \right ] \\ =& \sum_{j = 0}^{m - 1} \sum_{i = 0}^{n} \left [j + 1 \le \left \lfloor \frac{a i + b}{c} \right \rfloor \right] \\ =& \sum_{j = 0}^{m - 1} \sum_{i = 0}^{n} \left [cj + c - b \le a i \right ] \\ =& \sum_{j = 0}^{m - 1} \sum_{i = 0}^{n} \left [cj + c - b - 1 < a i \right ] \\ =& \sum_{j = 0}^{m - 1} \sum_{i = 0}^{n} \left [\left \lfloor \frac{cj + c - b - 1}{a} \right \rfloor < i \right ] \\ =& \sum_{j = 0}^{m - 1} n - \left \lfloor \frac{cj + c - b - 1}{a} \right \rfloor \\ =& nm - f(m - 1, c, c - b - 1, a) \end{aligned} $$

可以发现，最终 $a$ 和 $c$ 的位置将进行交换，也就类似于辗转相除的过程。因此，其复杂度为 $\mathcal O(n \log n)$，与欧几里得算法相同。

计算 $f(n, a, b, c)$ 的参考代码如下：

变体

观察标准 floor sum 的变体 $g(n, a, b, c)$ 和 $h(n, a, b, c)$，定义如下：

$$ g(n, a, b, c) = \sum_{i = 0}^{n} \left \lfloor \frac{a i + b}{c} \right \rfloor ^2 \\ h(n, a, b, c) = \sum_{i = 0}^{n} i \left \lfloor \frac{a i + b}{c} \right \rfloor $$

g

类似求 $f(n, a, b, c)$ 的过程，先将 $a$ 和 $b$ 对 $c$ 取模。

$$ \begin{aligned} g(n, a, b, c) =& \sum_{i = 0}^{n} \left \lfloor \frac{a i + b}{c} \right \rfloor ^2 \\ =& \sum_{i = 0}^{n} \left \lfloor \frac{(\left \lfloor \frac{a}{c} \right \rfloor c + a \bmod c) i + \left \lfloor \frac{b}{c} \right \rfloor + b \bmod c}{c} \right \rfloor ^2 \\ =& \sum_{i = 0}^{n} \left ( \left \lfloor \frac{a}{c} \right \rfloor i + \left \lfloor \frac{b}{c} \right \rfloor + \left \lfloor \frac{(a \bmod c) i + b \bmod c}{c} \right \rfloor \right ) ^2 \\ =& \frac{n(n + 1)(2n + 1)}{6} \left \lfloor \frac{a}{c} \right \rfloor ^2 + (n + 1) \left \lfloor \frac{b}{c} \right \rfloor ^2 + g(n, a \bmod c, b \bmod c, c) \\ +& \ n(n + 1) \left \lfloor \frac{a}{c} \right \rfloor \left \lfloor \frac{b}{c} \right \rfloor + 2 \left \lfloor \frac{a}{c} \right \rfloor h(n, a \bmod c, b \bmod c, c) + 2 \left \lfloor \frac{b}{c} \right \rfloor f(n, a \bmod c, b \bmod c, c) \end{aligned} $$

再考虑将 $a$ 和 $c$ 的位置进行交换。部分过程同 $f$ 的推导，故省略。

$$ \begin{aligned} g(n, a, b, c) =& \sum_{i = 0}^{n} \left \lfloor \frac{a i + b}{c} \right \rfloor ^2 \\ =& \sum_{i = 0}^{n} \sum_{j = 0}^{\left \lfloor \frac{a i + b}{c} \right \rfloor - 1} 2j + 1 \\ =& \sum_{j = 0}^{m - 1} \left (n - \left \lfloor \frac{cj + c - b - 1}{a} \right \rfloor \right ) (2j + 1) \\ =& nm^2 - 2h(m - 1, c, c - b - 1, a) - f(m - 1, c, c - b - 1, a) \end{aligned} $$

跟其他人推出来式子的不太一样，但本质上是相同的。

h

$$ \begin{aligned} h(n, a, b, c) =& \sum_{i = 0}^{n} i \left \lfloor \frac{a i + b}{c} \right \rfloor \\ =& \frac{n(n + 1)(2n + 1)}{6} \left \lfloor \frac{a}{c} \right \rfloor + \frac{n(n + 1)}{2} \left \lfloor \frac{b}{c} \right \rfloor + h(n, a \bmod c, b \bmod c, c) \end{aligned} $$

方便起见，令 $t = \left \lfloor \frac{cj + c - b - 1}{a} \right \rfloor$。

$$ \begin{aligned} h(n, a, b, c) =& \sum_{i = 0}^{n} i \left \lfloor \frac{a i + b}{c} \right \rfloor \\ =& \sum_{j = 0}^{m - 1} \sum_{i = 0}^{n} [i > t] \cdot i \\ =& \sum_{j = 0}^{m - 1} \frac{1}{2} (n - t) (n + t + 1) \\ =& \frac{1}{2} \left [ nm(n + 1) - g(m - 1, c, c - b - 1, a) - f(m - 1, c, c - b - 1, a) \right ] \end{aligned} $$

注意到计算 $f, g, h$ 的过程中，递归调用的方式都是相同的，因此可以将其打包进行计算。

万能欧几里得算法

类欧几里得算法较为麻烦的地方，在于其对于不同的 floor sum 变体，都需要重新推一遍式子，容易出错。

而万能欧几里得算法则对各类 floor sum 问题的变体，给出了一种更为通用的方法，而代价是常数更大，尽管在大多数情况下并不会被特意去卡。

其实先学了万欧再学的类欧的，笔记先咕咕咕了。

---