Oct 18, 2018

浅谈类欧几里德算法

本文数学公式较长，建议在屏幕较大的设备上阅读。

简介

类欧几里德算法即使用与欧几里德算法类似的思想解决一类求和式的计算问题。可用类欧几里德算法解决的求和式主要有以下三种：

f(a,b,c,n)=∑i=0n⌊ai+bc⌋g(a,b,c,n)=∑i=0ni⌊ai+bc⌋h(a,b,c,n)=∑i=0n⌊ai+bc⌋2 \begin{aligned} f(a, b, c, n) & = \sum\limits_{i = 0}^{n} {\left\lfloor \frac{ai + b}{c} \right\rfloor} \\ g(a, b, c, n) & = \sum\limits_{i = 0}^{n} {i \left\lfloor \frac{ai + b}{c} \right\rfloor} \\ h(a, b, c, n) & = \sum\limits_{i = 0}^{n} {\left\lfloor \frac{ai + b}{c} \right\rfloor}^2 \end{aligned}

后文中将简称它们为 ff 式，gg 式与 hh 式。

引理

考虑 a,b,ca, b, c 均为非负整数。

a≤⌊cb⌋⇔ab≤c a \le \left\lfloor \frac{c}{b} \right\rfloor \Leftrightarrow ab \le c

证明比较显然，这里就略去了。

a<⌊cb⌋⇔ab<c−b+1 a < \left\lfloor \frac{c}{b} \right\rfloor \Leftrightarrow ab < c - b + 1

下面给出简略证明过程：

a<⌊cb⌋⇔a≤⌊cb⌋−1⇔ab≤c−b⇔ab<c−b+1 \begin{aligned} a < \left\lfloor \frac{c}{b} \right\rfloor & \Leftrightarrow a \le \left\lfloor \frac{c}{b} \right\rfloor - 1 \\ & \Leftrightarrow ab \le c - b \\ & \Leftrightarrow ab < c - b + 1 \end{aligned}

n2=2⋅12(n−1)n+n=2∑i=0n−1i+n \begin{aligned} n^2 = & 2 \cdot \frac{1}{2}(n - 1)n + n \\ = & 2 \sum\limits_{i = 0}^{n - 1} {i} + n \end{aligned}

在后面的推导中可能会不加证明地使用上述三个结论。

f 式

形式

f(a,b,c,n)=∑i=0n⌊ai+bc⌋ f(a, b, c, n) = \sum\limits_{i = 0}^{n} {\left\lfloor \frac{ai + b}{c} \right\rfloor}

推导

首先我们考虑求和式中每一项都大于 00 的情况，即当 a≥ca \ge c 或 b≥cb \ge c 时：

f(a,b,c,n)=∑i=0n⌊ai+bc⌋=∑i=0n[⌊ac⌋i+⌊bc⌋+⌊(a mod c)i+(b mod c)c⌋]=⌊ac⌋∑i=0ni+⌊bc⌋∑i=0n1+∑i=0n⌊(a mod c)i+(b mod c)c⌋=⌊ac⌋12n(n+1)+⌊bc⌋(n+1)+f(a mod c,b mod c,c,n) \begin{aligned} f(a, b, c, n) & = \sum\limits_{i = 0}^{n} {\left\lfloor \frac{ai + b}{c} \right\rfloor} \\ & = \sum\limits_{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]} \\ & = \left\lfloor \frac{a}{c} \right\rfloor \sum\limits_{i = 0}^{n} {i} + \left\lfloor \frac{b}{c} \right\rfloor \sum\limits_{i = 0}^{n} {1} + \sum\limits_{i = 0}^{n} {\left\lfloor \frac{(a \bmod c)i + (b \bmod c)}{c} \right\rfloor} \\ & = \left\lfloor \frac{a}{c} \right\rfloor \frac{1}{2}n(n + 1) + \left\lfloor \frac{b}{c} \right\rfloor (n + 1) + f(a \bmod c, b \bmod c, c, n) \end{aligned}

接下来我们考虑存在某些项等于 00 的情况，即当 a,b<ca, b < c 时：

f(a,b,c,n)=∑i=0n⌊ai+bc⌋=∑i=0n∑j=0⌊ai+bc⌋−11=∑j=0⌊an+bc⌋−1∑i=0n(j≤⌊ai+bc⌋−1)=∑j=0⌊an+bc⌋−1∑i=0n(j<⌊ai+bc⌋) \begin{aligned} f(a, b, c, n) & = \sum\limits_{i = 0}^{n} {\left\lfloor \frac{ai + b}{c} \right\rfloor} \\ & = \sum\limits_{i = 0}^{n} \sum\limits_{j = 0}^{\left\lfloor \frac{ai + b}{c} \right\rfloor - 1} {1} \\ & = \sum_{j = 0}^{\left\lfloor \frac{an + b}{c} \right\rfloor - 1} \sum\limits_{i = 0}^{n} {(j \le \left\lfloor \frac{ai + b}{c} \right\rfloor - 1)} \\ & = \sum_{j = 0}^{\left\lfloor \frac{an + b}{c} \right\rfloor - 1} \sum\limits_{i = 0}^{n} {(j < \left\lfloor \frac{ai + b}{c} \right\rfloor)} \end{aligned}

我们不妨令 m=⌊an+bc⌋m = \left\lfloor \frac{an + b}{c} \right\rfloor，则有：

f(a,b,c,n)=∑j=0m−1∑i=0n(j<⌊ai+bc⌋)=∑j=0m−1∑i=0n[cj<(ai+b)−c+1]=∑j=0m−1∑i=0n(i>⌊cj+c−b−1a⌋) \begin{aligned} f(a, b, c, n) & = \sum_{j = 0}^{m - 1} \sum\limits_{i = 0}^{n} {(j < \left\lfloor \frac{ai + b}{c} \right\rfloor)} \\ & = \sum_{j = 0}^{m - 1} \sum\limits_{i = 0}^{n} {\left[ cj < (ai + b) - c + 1 \right]} \\ & = \sum\limits_{j = 0}^{m - 1} \sum\limits_{i = 0}^{n} {(i > \left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor)} \end{aligned}

不难发现，∑i=0n(⌊cj+c−b−1a⌋<i)\sum\limits_{i = 0}^{n} {(\left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor < i)} 即为 n−⌊cj+c−b−1a⌋n - \left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor。故有：

f(a,b,c,n)=∑j=0m−1(n−⌊cj+c−b−1a⌋)=nm−∑j=0m−1⌊cj+c−b−1a⌋=nm−f(c,c−b−1,a,m−1) \begin{aligned} f(a, b, c, n) & = \sum\limits_{j = 0}^{m - 1} {(n - \left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor)} \\ & = nm - \sum\limits_{j = 0}^{m - 1} {\left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor} \\ & = nm - f(c, c - b - 1, a, m - 1) \end{aligned}

现在假设我们有 f(a,b,c,n)f(a, b, c, n)，其中 a≥ca \ge c。经过情况 11 中的一次运算后 (a,b,c,n)(a, b, c, n) 变为 (a mod c,b mod c,c,n)(a \bmod c, b \bmod c, c, n)。此时我们再应用情况 22 进行一次运算四个参数就变成了 (c,c−b mod c−1,a mod c,m−1)(c, c - b \bmod c - 1, a \bmod c, m - 1)。我们注意观察第 11 个参数和第 33 个参数，经过上述两次运算后由 (a,c)(a, c) 变成了 (c,a mod c)(c, a \bmod c)。这与欧几里德算法存在极大的相似之处，因此我们把这种算法称作类欧几里德算法。至于时间复杂度，显然也是与欧几里德算法相同的，为 O(log⁡n)\mathcal{O}(\log{n}) 级别。

结论

令 m=⌊an+bc⌋m = \left\lfloor \frac{an + b}{c} \right\rfloor，有：

f(a,b,c,n)={⌊ac⌋n(n+1)2+⌊bc⌋(n+1)+f(a mod c,b mod c,c,n)a≥c∨b≥cnm−f(c,c−b−1,a,m−1)otherwise f(a, b, c, n) = \begin{cases} \left\lfloor \frac{a}{c} \right\rfloor \frac{n(n + 1)}{2} + \left\lfloor \frac{b}{c} \right\rfloor (n + 1) & \\ + f(a \bmod c, b \bmod c, c, n) & a \ge c \lor b \ge c \\ nm - f(c, c - b - 1, a, m - 1) & \text{otherwise} \end{cases}

g 式

形式

g(a,b,c,n)=∑i=0ni⌊ai+bc⌋ g(a, b, c, n) = \sum\limits_{i = 0}^{n} {i \left\lfloor \frac{ai + b}{c} \right\rfloor}

推导

若 a≥ca \ge c 或 b≥cb \ge c，有：

g(a,b,c,n)=∑i=0ni⌊ai+bc⌋=∑i=0ni⋅(⌊ac⌋i+⌊bc⌋+⌊(a mod c)i+(b mod c)c⌋)=⌊ac⌋∑i=0ni2+⌊bc⌋∑i=0ni+∑i=0ni⌊(a mod c)i+(b mod c)c⌋=⌊ac⌋16n(n+1)(2n+1)+⌊bc⌋12n(n+1)+g(a mod c,b mod c,c,n) \begin{aligned} g(a, b, c, n) & = \sum\limits_{i = 0}^{n} {i \left\lfloor \frac{ai + b}{c} \right\rfloor} \\ & = \sum\limits_{i = 0}^{n} {i \cdot ( \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)} \\ & = \left\lfloor \frac{a}{c} \right\rfloor \sum\limits_{i = 0}^{n} {i^2} + \left\lfloor \frac{b}{c} \right\rfloor\sum\limits_{i = 0}^{n} {i} + \sum\limits_{i = 0}^{n} {i \left\lfloor \frac{(a \bmod c)i + (b \bmod c)}{c} \right\rfloor} \\ & = \left\lfloor \frac{a}{c} \right\rfloor \frac{1}{6}n(n + 1)(2n + 1) + \left\lfloor \frac{b}{c} \right\rfloor \frac{1}{2}n(n + 1) + g(a \bmod c, b \bmod c, c, n) \end{aligned}

若 a,b<ca, b < c，有：

g(a,b,c,n)=∑i=0ni⌊ai+bc⌋=∑i=0n∑j=0⌊ai+bc⌋−1i=∑j=0⌊an+bc⌋−1∑i=0ni⋅(j≤⌊ai+bc⌋−1)=∑j=0⌊an+bc⌋−1∑i=0ni⋅(j<⌊ai+bc⌋)let m=⌊an+bc⌋=∑j=0m−1∑i=0ni⋅(j<⌊ai+bc⌋)=∑j=0m−1∑i=0ni⋅[cj<(ai+b)−c+1]=∑j=0m−1∑i=0ni⋅(i>⌊cj+c−b−1a⌋) \begin{aligned} g(a, b, c, n) & = \sum\limits_{i = 0}^{n} {i \left\lfloor \frac{ai + b}{c} \right\rfloor} \\ & = \sum\limits_{i = 0}^{n} \sum\limits_{j = 0}^{\left\lfloor \frac{ai + b}{c} \right\rfloor - 1} {i} \\ & = \sum_{j = 0}^{\left\lfloor \frac{an + b}{c} \right\rfloor - 1} \sum\limits_{i = 0}^{n} {i \cdot (j \le \left\lfloor \frac{ai + b}{c} \right\rfloor - 1)} \\ & = \sum_{j = 0}^{\left\lfloor \frac{an + b}{c} \right\rfloor - 1} \sum\limits_{i = 0}^{n} {i \cdot (j < \left\lfloor \frac{ai + b}{c} \right\rfloor)} & \text{let } m = \left\lfloor \frac{an + b}{c} \right\rfloor \\ & = \sum_{j = 0}^{m - 1} \sum\limits_{i = 0}^{n} {i \cdot (j < \left\lfloor \frac{ai + b}{c} \right\rfloor)} \\ & = \sum_{j = 0}^{m - 1} \sum\limits_{i = 0}^{n} {i \cdot \left[ cj < (ai + b) - c + 1 \right]} \\ & = \sum_{j = 0}^{m - 1} \sum\limits_{i = 0}^{n} {i \cdot (i > \left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor)} \end{aligned}

不难发现，∑i=0ni⋅(⌊cj+c−b−1a⌋<i)\sum\limits_{i = 0}^{n} {i \cdot (\left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor < i)} 可看作一个首项为 ⌊cj+c−b−1a⌋+1\left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor + 1，末项为 nn 的等差数列求和，即等于 12⋅(⌊cj+c−b−1a⌋+1+n)⋅(n−⌊cj+c−b−1a⌋)\frac{1}{2} \cdot(\left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor + 1 + n) \cdot (n - \left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor)。故有：

g(a,b,c,n)=∑j=0m−112(⌊cj+c−b−1a⌋+n+1)⋅(n−⌊cj+c−b−1a⌋)=12∑j=0m−1[n(n+1)−⌊cj+c−b−1a⌋2−⌊cj+c−b−1a⌋]=12[∑j=0m−1n(n+1)−∑j=0m−1⌊cj+c−b−1a⌋2−∑j=0m−1⌊cj+c−b−1a⌋]=12[mn(n+1)−h(c,c−b−1,a,m−1)−f(c,c−b−1,a,m−1)] \begin{aligned} g(a, b, c, n) & = \sum\limits_{j = 0}^{m - 1} {\frac{1}{2} (\left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor + n + 1) \cdot (n - \left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor)} \\ & = \frac{1}{2} \sum\limits_{j = 0}^{m - 1} {\left[ n(n + 1) - {\left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor}^2 - \left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor \right]} \\ & = \frac{1}{2} \left[ \sum\limits_{j = 0}^{m - 1} {n(n + 1)} - \sum\limits_{j = 0}^{m - 1} {\left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor}^2 - \sum\limits_{j = 0}^{m - 1} {\left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor} \right] \\ & = \frac{1}{2} \left[ mn(n + 1) - h(c, c - b - 1, a, m - 1) - f(c, c - b - 1, a, m - 1) \right] \end{aligned}

看来 gg 式最后推出来还会跟 hh 式有关系……

结论

令 m=⌊an+bc⌋m = \left\lfloor \frac{an + b}{c} \right\rfloor，有：

g(a,b,c,n)={⌊ac⌋16n(n+1)(2n+1)+⌊bc⌋12n(n+1)+g(a mod c,b mod c,c,n)a≥c∨b≥c12[mn(n+1)−h(c,c−b−1,a,m−1)−f(c,c−b−1,a,m−1)]otherwise g(a, b, c, n) = \begin{cases} \left\lfloor \frac{a}{c} \right\rfloor \frac{1}{6}n(n + 1)(2n + 1) + \left\lfloor \frac{b}{c} \right\rfloor \frac{1}{2}n(n + 1) & \\ + g(a \bmod c, b \bmod c, c, n) & a \ge c \lor b \ge c \\ \frac{1}{2} \left[ mn(n + 1) - h(c, c - b - 1, a, m - 1) - f(c, c - b - 1, a, m - 1) \right] & \text{otherwise} \end{cases}

h 式

形式

h(a,b,c,n)=∑i=0n⌊ai+bc⌋2 h(a, b, c, n) = \sum\limits_{i = 0}^{n} {\left\lfloor \frac{ai + b}{c} \right\rfloor}^2

推导

若 a≥ca \ge c 或 b≥cb \ge c，有：

h(a,b,c,n)=∑i=0n⌊ai+bc⌋2=∑i=0n(⌊ac⌋i+⌊bc⌋+⌊(a mod c)i+(b mod c)c⌋)2=∑i=0n(⌊ac⌋i+⌊bc⌋)2+2∑i=0n(⌊ac⌋i+⌊bc⌋)⋅⌊(a mod c)i+(b mod c)c⌋+∑i=0n⌊(a mod c)i+(b mod c)c⌋2 \begin{aligned} h(a, b, c, n) & = \sum\limits_{i = 0}^{n} {\left\lfloor \frac{ai + b}{c} \right\rfloor}^2 \\ & = \sum\limits_{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)^2} \\ & = \sum\limits_{i = 0}^{n} {(\left\lfloor \frac{a}{c} \right\rfloor i + \left\lfloor \frac{b}{c} \right\rfloor)^2} + 2 \sum\limits_{i = 0}^{n} (\left\lfloor \frac{a}{c} \right\rfloor i + \left\lfloor \frac{b}{c} \right\rfloor) \cdot \left\lfloor \frac{(a \bmod c)i + (b \bmod c)}{c} \right\rfloor \\ & + \sum\limits_{i = 0}^{n} {\left\lfloor \frac{(a \bmod c)i + (b \bmod c)}{c} \right\rfloor}^2 \end{aligned}

为了方便展示，分开化简这三项：

∑i=0n(⌊ac⌋i+⌊bc⌋)2=⌊ac⌋2∑i=0ni2+2⌊ac⌋⌊bc⌋∑i=0ni+⌊bc⌋2∑i=0n1=⌊ac⌋216n(n+1)(2n+1)+⌊ac⌋⌊bc⌋2n(n+1)+⌊bc⌋2(n+1)2∑i=0n(⌊ac⌋i+⌊bc⌋)⌊(a mod c)i+(b mod c)c⌋=2⌊ac⌋∑i=0ni⌊(a mod c)i+(b mod c)c⌋+2⌊bc⌋∑i=0n⌊(a mod c)i+(b mod c)c⌋=2⌊ac⌋g(a mod c,b mod c,c,n)+2⌊bc⌋f(a mod c,b mod c,c,n)∑i=0n⌊(a mod c)i+(b mod c)c⌋2=h(a mod c,b mod c,c,n) \begin{aligned} \sum\limits_{i = 0}^{n} & {(\left\lfloor \frac{a}{c} \right\rfloor i + \left\lfloor \frac{b}{c} \right\rfloor)^2} \\ = & \left\lfloor \frac{a}{c} \right\rfloor^2 \sum\limits_{i = 0}^{n} {i^2} + 2\left\lfloor \frac{a}{c} \right\rfloor \left\lfloor \frac{b}{c} \right\rfloor \sum\limits_{i = 0}^{n} {i} + {\left\lfloor \frac{b}{c} \right\rfloor}^2 \sum\limits_{i = 0}^{n} {1} \\ = & \left\lfloor \frac{a}{c} \right\rfloor^2 \frac{1}{6}n(n + 1)(2n + 1) + \left\lfloor \frac{a}{c} \right\rfloor \left\lfloor \frac{b}{c} \right\rfloor 2n(n + 1) + \left\lfloor \frac{b}{c} \right\rfloor^2 (n + 1) \\ \\ 2\sum\limits_{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 \\ = & 2\left\lfloor \frac{a}{c} \right\rfloor \sum\limits_{i = 0}^{n} {i\left\lfloor \frac{(a \bmod c)i + (b \bmod c)}{c} \right\rfloor} + 2\left\lfloor \frac{b}{c} \right\rfloor \sum\limits_{i = 0}^{n} {\left\lfloor \frac{(a \bmod c)i + (b \bmod c)}{c} \right\rfloor} \\ = & 2\left\lfloor \frac{a}{c} \right\rfloor g(a \bmod c, b \bmod c, c, n) + 2\left\lfloor \frac{b}{c} \right\rfloor f(a \bmod c, b \bmod c, c, n) \\ \\ \sum\limits_{i = 0}^{n} & {\left\lfloor \frac{(a \bmod c)i + (b \bmod c)}{c} \right\rfloor}^2 \\ = & h(a \bmod c, b \bmod c, c, n) \end{aligned}

加起来并整理后有：

h(a,b,c,n)=⌊ac⌋216n(n+1)(2n+1)+⌊ac⌋⌊bc⌋2n(n+1)+⌊bc⌋2(n+1)+2⌊ac⌋g(a mod c,b mod c,c,n)+2⌊bc⌋f(a mod c,b mod c,c,n)+h(a mod c,b mod c,c,n) \begin{aligned} h & (a, b, c, n) \\ & = \left\lfloor \frac{a}{c} \right\rfloor^2 \frac{1}{6}n(n + 1)(2n + 1) + \left\lfloor \frac{a}{c} \right\rfloor \left\lfloor \frac{b}{c} \right\rfloor 2n(n + 1) + \left\lfloor \frac{b}{c} \right\rfloor^2 (n + 1) \\ & + 2\left\lfloor \frac{a}{c} \right\rfloor g(a \bmod c, b \bmod c, c, n) + 2\left\lfloor \frac{b}{c} \right\rfloor f(a \bmod c, b \bmod c, c, n) \\ & + h(a \bmod c, b \bmod c, c, n) \end{aligned}

若 a,b<ca, b < c，有：

h(a,b,c,n)=∑i=0n⌊ai+bc⌋2=∑i=0n(2∑j=0⌊ai+bc⌋−1j+⌊ai+bc⌋)=2∑j=0⌊an+bc⌋−1∑i=0nj⋅(j≤⌊ai+bc⌋−1)+∑i=0n⌊ai+bc⌋=2∑j=0⌊an+bc⌋−1∑i=0nj⋅(j<⌊ai+bc⌋)+f(a,b,c,n)let m=⌊an+bc⌋=2∑j=0m−1∑i=0nj⋅(j<⌊ai+bc⌋)+f(a,b,c,n)=2∑j=0m−1j⋅∑i=0n[cj<(ai+b)−c+1]+f(a,b,c,n)=2∑j=0m−1j⋅∑i=0n(⌊cj+c−b−1a⌋<i)+f(a,b,c,n)=2∑j=0m−1j⋅(n−⌊cj+c−b−1a⌋)+f(a,b,c,n)=2n∑j=0m−1j−2∑j=0m−1j⋅⌊cj+c−b−1a⌋+f(a,b,c,n)=2n⋅12(m−1)m−2g(c,c−b−1,a,m−1)+f(a,b,c,n) \begin{aligned} h(a, b, c, n) & = \sum\limits_{i = 0}^{n} {\left\lfloor \frac{ai + b}{c} \right\rfloor}^2 \\ & = \sum\limits_{i = 0}^{n} (2 \sum\limits_{j= 0}^{\left\lfloor \frac{ai + b}{c} \right\rfloor - 1} {j} + \left\lfloor \frac{ai + b}{c} \right\rfloor) \\ & = 2\sum\limits_{j = 0}^{\left\lfloor \frac{an + b}{c} \right\rfloor - 1} \sum\limits_{i = 0}^{n} {j \cdot (j \le \left\lfloor \frac{ai + b}{c} \right\rfloor - 1)} + \sum\limits_{i = 0}^{n} {\left\lfloor \frac{ai + b}{c} \right\rfloor} \\ & = 2\sum\limits_{j = 0}^{\left\lfloor \frac{an + b}{c} \right\rfloor - 1} \sum\limits_{i = 0}^{n} {j \cdot (j < \left\lfloor \frac{ai + b}{c} \right\rfloor)} + f(a, b, c, n) \\ & \text{let } m = \left\lfloor \frac{an + b}{c} \right\rfloor \\ & = 2\sum\limits_{j = 0}^{m - 1} \sum\limits_{i = 0}^{n} {j \cdot (j < \left\lfloor \frac{ai + b}{c} \right\rfloor)} + f(a, b, c, n) \\ & = 2\sum\limits_{j = 0}^{m - 1} j \cdot \sum\limits_{i = 0}^{n} {\left[ cj < (ai + b) - c + 1 \right]} + f(a, b, c, n) \\ & = 2\sum\limits_{j = 0}^{m - 1} j \cdot \sum\limits_{i = 0}^{n} {(\left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor < i)} + f(a, b, c, n) \\ & = 2\sum\limits_{j = 0}^{m - 1} j \cdot (n - \left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor) + f(a, b, c, n) \\ & = 2n\sum\limits_{j = 0}^{m - 1} {j} - 2\sum\limits_{j = 0}^{m - 1} {j \cdot \left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor} + f(a, b, c, n) \\ & = 2n \cdot \frac{1}{2}(m - 1)m - 2g(c, c - b - 1, a, m - 1) + f(a, b, c, n) \end{aligned}

带入之前推 ff 式得到的结论可得：

h(a,b,c,n)=n(m−1)m−2g(c,c−b−1,a,m−1)+nm−f(c,c−b−1,a,m−1)=nm2−2g(c,c−b−1,a,m−1)−f(c,c−b−1,a,m−1) \begin{aligned} h(a, b, c, n) & = n(m - 1)m - 2g(c, c - b - 1, a, m - 1) \\ & + nm - f(c, c - b - 1, a, m - 1) \\ & = nm^2 - 2g(c, c - b - 1, a, m - 1) - f(c, c - b - 1, a, m - 1) \end{aligned}

结论

令 m=⌊an+bc⌋m = \left\lfloor \frac{an + b}{c} \right\rfloor，有：

h(a,b,c,n)={⌊ac⌋216n(n+1)(2n+1)+⌊ac⌋⌊bc⌋2n(n+1)+⌊bc⌋2(n+1) +2⌊ac⌋g(a mod c,b mod c,c,n)+2⌊bc⌋f(a mod c,b mod c,c,n) +h(a mod c,b mod c,c,n)a≥c∨b≥cnm2−2g(c,c−b−1,a,m−1)−f(c,c−b−1,a,m−1)otherwise h(a, b, c, n) = \begin{cases} \left\lfloor \frac{a}{c} \right\rfloor^2 \frac{1}{6}n(n + 1)(2n + 1) + \left\lfloor \frac{a}{c} \right\rfloor \left\lfloor \frac{b}{c} \right\rfloor 2n(n + 1) + \left\lfloor \frac{b}{c} \right\rfloor^2(n + 1) & \\ \ + 2\left\lfloor \frac{a}{c} \right\rfloor g(a \bmod c, b \bmod c, c, n) + 2\left\lfloor \frac{b}{c} \right\rfloor f(a \bmod c, b \bmod c, c, n) & \\ \ + h(a \bmod c, b \bmod c, c, n) & a \ge c \lor b \ge c \\ nm^2 - 2g(c, c - b - 1, a, m - 1) - f(c, c - b - 1, a, m - 1) & \text{otherwise} \end{cases}

代码实现

仅 f 式

long long int quasiEuclidean(long long int a, long long int b, 
                            long long int c, long long int n) {
    if (a == 0) {
        return (n + 1) * (b / c);
    }

    if (a >= c || b >= c) {
        long long int tmp = (n & 1) ? ((n + 1) >> 1) * n : (n >> 1) * (n + 1);
        return (a / c) * tmp + (b / c) * (n + 1) + quasiEuclidean(a % c, b % c, c, n);
    }

    long long int m = (a * n + b) / c;
    return n * m - quasiEuclidean(c, c - b - 1, a, m - 1);
}

f, g, h 式

由于没有找到相应的模板题，所以…… 咕咕咕……

更通用的情况

在讨论完 f,g,hf, g, h 式的推导后，我们来看一种更加通用的情况：

∑i=0nik1⌊ai+bc⌋k2 \sum\limits_{i = 0}^{n} {i^{k_1} \left\lfloor \frac{ai + b}{c} \right\rfloor ^{k_2}} 题目链接：类欧几里得算法 - 题目 - LibreOJ

咕咕咕……