类欧几里得算法学习笔记

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

f(a,b,c,n)=i=0nai+bcf(a, b, c, n) = \sum_{i = 0}^{n} \lfloor \frac{ai + b}{c} \rfloor

g(a,b,c,n)=i=0niai+bcg(a, b, c, n) = \sum_{i = 0}^{n} i\lfloor \frac{ai + b}{c} \rfloor

h(a,b,c,n)=i=0nai+bc2h(a, b, c, n) = \sum_{i = 0}^{n} \lfloor \frac{ai + b}{c} \rfloor ^2

并定义:

m=an+bcm = \lfloor \frac{an + b}{c} \rfloor

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

函数 fff 的处理

aca \geq cbcb \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<ca < cb<cb < 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}

函数 ggg 的处理

aca \geq cbcb \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<ca < cb<cb < 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}

函数 hhh 的处理

aca \geq cbcb \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<ca < cb<cb < c 时:

\begin{align} \because ~& n^2 = 2 \times \frac{n(n + 1)}{2} - n = 2\sum_{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}