浅谈类欧几里德算法

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

简介

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

f(a,b,c,n)=i=0nai+bcg(a,b,c,n)=i=0niai+bch(a,b,c,n)=i=0nai+bc2\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 均为非负整数。

#1

acbabca \le \left\lfloor \frac{c}{b} \right\rfloor \Leftrightarrow ab \le c

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

#2

a<cbab<cb+1a < \left\lfloor \frac{c}{b} \right\rfloor \Leftrightarrow ab < c - b + 1

下面给出简略证明过程:

a<cbacb1abcbab<cb+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}

#3

n2=212(n1)n+n=2i=0n1i+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=0nai+bcf(a, b, c, n) = \sum\limits_{i = 0}^{n} {\left\lfloor \frac{ai + b}{c} \right\rfloor}

推导

首先我们考虑求和式中每一项都大于 00 的情况,即当 aca \ge cbcb \ge c 时:

f(a,b,c,n)=i=0nai+bc=i=0n[aci+bc+(amodc)i+(bmodc)c]=aci=0ni+bci=0n1+i=0n(amodc)i+(bmodc)c=ac12n(n+1)+bc(n+1)+f(amodc,bmodc,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=0nai+bc=i=0nj=0ai+bc11=j=0an+bc1i=0n(jai+bc1)=j=0an+bc1i=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+bcm = \left\lfloor \frac{an + b}{c} \right\rfloor,则有:

f(a,b,c,n)=j=0m1i=0n(j<ai+bc)=j=0m1i=0n[cj<(ai+b)c+1]=j=0m1i=0n(i>cj+cb1a)\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+cb1a<i)\sum\limits_{i = 0}^{n} {(\left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor < i)} 即为 ncj+cb1an - \left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor。故有:

f(a,b,c,n)=j=0m1(ncj+cb1a)=nmj=0m1cj+cb1a=nmf(c,cb1,a,m1)\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),其中 aca \ge c。经过情况 11 中的一次运算后 (a,b,c,n)(a, b, c, n) 变为 (amodc,bmodc,c,n)(a \bmod c, b \bmod c, c, n)。此时我们再应用情况 22 进行一次运算四个参数就变成了 (c,cbmodc1,amodc,m1)(c, c - b \bmod c - 1, a \bmod c, m - 1)。我们注意观察第 11 个参数和第 33 个参数,经过上述两次运算后由 (a,c)(a, c) 变成了 (c,amodc)(c, a \bmod c)。这与欧几里德算法存在极大的相似之处,因此我们把这种算法称作类欧几里德算法。至于时间复杂度,显然也是与欧几里德算法相同的,为 O(logn)\mathcal{O}(\log{n}) 级别。

结论

m=an+bcm = \left\lfloor \frac{an + b}{c} \right\rfloor,有:

f(a,b,c,n)={acn(n+1)2+bc(n+1)+f(amodc,bmodc,c,n)acbcnmf(c,cb1,a,m1)otherwisef(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=0niai+bcg(a, b, c, n) = \sum\limits_{i = 0}^{n} {i \left\lfloor \frac{ai + b}{c} \right\rfloor}

推导

aca \ge cbcb \ge c,有:

g(a,b,c,n)=i=0niai+bc=i=0ni(aci+bc+(amodc)i+(bmodc)c)=aci=0ni2+bci=0ni+i=0ni(amodc)i+(bmodc)c=ac16n(n+1)(2n+1)+bc12n(n+1)+g(amodc,bmodc,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=0niai+bc=i=0nj=0ai+bc1i=j=0an+bc1i=0ni(jai+bc1)=j=0an+bc1i=0ni(j<ai+bc)\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)} \
\end{aligned}

我们依然记 m=an+bcm = \left\lfloor \frac{an + b}{c} \right\rfloor,则有:

g(a,b,c,n)=j=0m1i=0ni(j<ai+bc)=j=0m1i=0ni[cj<(ai+b)c+1]=j=0m1i=0ni(i>cj+cb1a)\begin{aligned}
g(a, b, c, n)
& = \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+cb1a<i)\sum\limits_{i = 0}^{n} {i \cdot (\left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor < i)} 可看作一个首项为 cj+cb1a+1\left\lfloor \frac{cj + c - b - 1}{a} \right\rfloor + 1,末项为 nn 的等差数列求和,即等于 12(cj+cb1a+1+n)(ncj+cb1a)\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=0m112(cj+cb1a+n+1)(ncj+cb1a)=12j=0m1[n(n+1)cj+cb1a2cj+cb1a]=12[j=0m1n(n+1)j=0m1cj+cb1a2j=0m1cj+cb1a]=12[mn(n+1)h(c,cb1,a,m1)f(c,cb1,a,m1)]\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+bcm = \left\lfloor \frac{an + b}{c} \right\rfloor,有:

g(a,b,c,n)={ac16n(n+1)(2n+1)+bc12n(n+1)+g(amodc,bmodc,c,n)acbc12[mn(n+1)h(c,cb1,a,m1)f(c,cb1,a,m1)]otherwiseg(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=0nai+bc2h(a, b, c, n) = \sum\limits_{i = 0}^{n} {\left\lfloor \frac{ai + b}{c} \right\rfloor}^2

推导

aca \ge cbcb \ge c,有:

h(a,b,c,n)=i=0nai+bc2=i=0n(aci+bc+(amodc)i+(bmodc)c)2=i=0n(aci+bc)2+2i=0n(aci+bc)(amodc)i+(bmodc)c+i=0n(amodc)i+(bmodc)c2\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(aci+bc)2=ac2i=0ni2+2acbci=0ni+bc2i=0n1=ac216n(n+1)(2n+1)+acbc2n(n+1)+bc2(n+1)2i=0n(aci+bc)(amodc)i+(bmodc)c=2aci=0ni(amodc)i+(bmodc)c+2bci=0n(amodc)i+(bmodc)c=2acg(amodc,bmodc,c,n)+2bcf(amodc,bmodc,c,n)i=0n(amodc)i+(bmodc)c2=h(amodc,bmodc,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)=ac216n(n+1)(2n+1)+acbc2n(n+1)+bc2(n+1)+2acg(amodc,bmodc,c,n)+2bcf(amodc,bmodc,c,n)+h(amodc,bmodc,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=0nai+bc2=i=0n(2j=0ai+bc1j+ai+bc)=2j=0an+bc1i=0nj(jai+bc1)+i=0nai+bc=2j=0an+bc1i=0nj(j<ai+bc)+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) \
\end{aligned}

我们依然记 m=an+bcm = \left\lfloor \frac{an + b}{c} \right\rfloor,则有:

h(a,b,c,n)=2j=0m1i=0nj(j<ai+bc)+f(a,b,c,n)=2j=0m1ji=0n[cj<(ai+b)c+1]+f(a,b,c,n)=2j=0m1ji=0n(cj+cb1a<i)+f(a,b,c,n)=2j=0m1j(ncj+cb1a)+f(a,b,c,n)=2nj=0m1j2j=0m1jcj+cb1a+f(a,b,c,n)=2n12(m1)m2g(c,cb1,a,m1)+f(a,b,c,n)\begin{aligned}
h(a, b, c, n)
= & 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(m1)m2g(c,cb1,a,m1)+nmf(c,cb1,a,m1)=nm22g(c,cb1,a,m1)f(c,cb1,a,m1)\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+bcm = \left\lfloor \frac{an + b}{c} \right\rfloor,有:

h(a,b,c,n)={ac216n(n+1)(2n+1)+acbc2n(n+1)+bc2(n+1) +2acg(amodc,bmodc,c,n)+2bcf(amodc,bmodc,c,n) +h(amodc,bmodc,c,n)acbcnm22g(c,cb1,a,m1)f(c,cb1,a,m1)otherwiseh(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=0nik1ai+bck2\sum\limits_{i = 0}^{n} {i^{k_1} \left\lfloor \frac{ai + b}{c} \right\rfloor ^{k_2}}
题目链接:类欧几里得算法 - 题目 - LibreOJ

咕咕咕……

%%%

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/10/18/quasi-euclidean-algorithm/