类欧几里得算法学习笔记

类欧几里得算法用来求诸如此类问题：

$$f(a,b,c,n)=\sum\limits_{i=0}^{n} \lfloor\frac{ai + b}{c}\rfloor$$

分类讨论

第一种情况：$a=0​$ 。那么

$$f(a,b,c,n)= \sum\limits_{i=0}^{n} \lfloor \frac{b}{c} \rfloor=(n+1)\lfloor \frac{b}{c} \rfloor$$

第二种情况：$a,b$ 中有一个大于等于 $c$ 。那么

$$\begin{aligned} f(a,b,c,n) &= \sum\limits_{i=0}^{n} \lfloor\frac{ai + b}{c}\rfloor \\\ &= \sum\limits_{i = 0}^{n}(\lfloor\frac{a\bmod c\cdot i + b \bmod c}{c}\rfloor+i\lfloor\frac{a}{c} \rfloor+\lfloor \frac{b}{c} \rfloor) \\\ &= \sum\limits_{i = 0}^{n}\lfloor\frac{a\bmod c\cdot i + b \bmod c}{c}\rfloor +\frac{n(n+1)}{2} \cdot \lfloor\frac{a}{c} \rfloor + (n+1)\lfloor \frac{b}{c} \rfloor \\\ &= f(a\bmod c, b \bmod c , c, n) + \frac{n(n+1)}{2} \cdot \lfloor\frac{a}{c} \rfloor + (n+1)\lfloor \frac{b}{c} \rfloor \end{aligned}$$

第三种情况：$a<c$ 且 $b < c$ 。那么

$$\begin{aligned} f(a,b,c,n) &= \sum\limits_{i=0}^{n} \lfloor\frac{ai + b}{c}\rfloor \\\ &= \sum\limits_{i=0}^{n} \sum\limits_{j=0}^{\lfloor\frac{an + b}{c}\rfloor-1} [j+1 \leq \lfloor\frac{ai + b}{c}\rfloor] \\\ &= \sum\limits_{j=0}^{\lfloor\frac{an + b}{c}\rfloor-1}\sum\limits_{i=0}^{n} [c(j+1) <ai + b + 1] \\\ &= \sum\limits_{j=0}^{\lfloor\frac{an + b}{c}\rfloor-1}\sum\limits_{i=0}^{n} [i > \frac{cj+c-b-1}{a}] \\\ &= \sum\limits_{j=0}^{\lfloor\frac{an + b}{c}\rfloor-1}(n - \lfloor \frac{cj+c-b-1}{a} \rfloor) \\\ &= n \cdot \lfloor\frac{an + b}{c}\rfloor - \sum\limits_{j=0}^{\lfloor\frac{an + b}{c}\rfloor-1}\lfloor \frac{cj+c-b-1}{a} \rfloor \\\ &= n \cdot \lfloor\frac{an + b}{c}\rfloor - f(c, c - b - 1, a, \lfloor\frac{an + b}{c}\rfloor-1) \end{aligned}$$

递归计算即可 复杂度一个 $\log$