类欧几里得算法学习笔记

常见的用类欧几里得算法处理的几个函数：

[
f(a, b, c, n) = sum{i = 0}^{n} lfloor frac{ai + b}{c} rfloor
] [
g(a, b, c, n) = sum{i = 0}^{n} ilfloor frac{ai + b}{c} rfloor
] [
h(a, b, c, n) = sum_{i = 0}^{n} lfloor frac{ai + b}{c} rfloor ^2
]

并定义：

[
m = lfloor frac{an + b}{c} rfloor
]

可在 (O(log min(a, b))) 的时间内计算以上函数。

函数 (f) 的处理

当 (a geq c) 或 (b geq c) 时：

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

当 (a < c) 且 (b < c) 时：

[
begin{align}
f(a, b, c, n) &= sum{i = 0}^{n} sum{j = 1}^{m} [frac{ai + b}{c} geq j] \
&= sum{i = 0}^{n} sum{j = 0}^{m - 1} [ai geq c(j + 1) - b] \
&= sum{i = 0}^{n} sum{j = 0}^{m - 1} [ai > cj + c - b - 1] \
&= sum{i = 0}^{n} sum{j = 0}^{m - 1} [i > frac{cj + c - b - 1}{a}] \
&= sum{j = 0}^{m - 1} sum{i = 0}^{n} [i > frac{cj + c - b - 1}{a}] \
&= sum_{j = 0}^{m - 1} left( n - lfloor frac{cj + c - b - 1}{a} rfloor right) \
&= nm - f(c, c - b - 1, a, m - 1)
end{align}
]

函数 (g) 的处理

当 (a geq c) 或 (b geq c) 时：

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

当 (a < c) 且 (b < c) 时：

[
begin{align}
g(a, b, c, n) &= sum{i = 0}^{n} i sum{j = 1}^{m} [frac{ai + b}{c} geq j] \
&= sum{i = 0}^{n} i sum{j = 0}^{m - 1} [i > frac{cj + c - b - 1}{a}] \
&= sum{j = 0}^{m - 1} sum{i = 0}^{n} i [i > frac{cj + c - b - 1}{a}] \
&= sum{j = 0}^{m - 1} frac{1}{2} (n + 1 + lfloor frac{cj + c - b - 1}{a} rfloor) (n - lfloor frac{cj + c - b - 1}{a} rfloor) \
&= frac{1}{2} sum{j = 0}^{m - 1} left(n(n + 1) - lfloor frac{cj + c - b - 1}{a} rfloor - lfloor frac{cj + c - b - 1}{a} rfloor ^2 right) \
&= frac{1}{2} left( nm(n + 1) - f(c, c - b - 1, a, m - 1) - h(c, c - b - 1, a, m - 1) right)
end{align}
]

函数 (h) 的处理

当 (a geq c) 或 (b geq c) 时：

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

当 (a < c) 且 (b < c) 时：

[
begin{align}
because ~&
n^2 = 2 times frac{n(n + 1)}{2} - n = 2sum{i = 1}^{n}i - n \
therefore ~&
h(a, b, c, n) = sum{i = 0}^{n} (2 sum{j = 1}^{lfloor frac{ai + b}{c} rfloor} j - lfloor frac{ai + b}{c} rfloor)
end{align}
] [
begin{align}
h(a, b, c, n) &= sum{i = 0}^{n} (2 sum{j = 1}^{lfloor frac{ai + b}{c} rfloor} j - lfloor frac{ai + b}{c} rfloor) \
&= 2 sum{j = 0}^{m - 1} (j + 1) sum{i = 0}^{n} [frac{ai + b}{c} geq j + 1] - f(a, b, c, n) \
&= 2 sum{j = 0}^{m - 1} (j + 1) sum{i = 0}^{n} [i > frac{cj + c - b - 1}{a}] - f(a, b, c, n) \
&= 2 sum{j = 0}^{m - 1} (j + 1) (n - lfloor frac{cj + c - b - 1}{a} rfloor) - f(a, b, c, n) \
&= nm(m + 1) - 2g(c, c - b - 1, a, m - 1) - f(a, b, c, n)
end{align}
]