类欧几里得算法
基础
求
\[f(a,b,c,n)=\sum_{i=0}^n \left\lfloor \dfrac{ai+b}{c}\right\rfloor
\]
\(a\ge c\)或\(b\ge c\)
\[\begin{aligned}
f(a,b,c,n)&=\sum_{i=0}^n \left\lfloor \dfrac{ai+b}{c}\right\rfloor\&=\sum_{i=0}^n \left\lfloor \dfrac{c\left\lfloor\frac{a}{c}\right\rfloor i+a\bmod c\times i+c\left\lfloor\frac{b}{c}\right\rfloor+b\bmod c}{c}\right\rfloor\&=\sum_{i=0}^n\left\lfloor\dfrac{a}{c}\right\rfloor i+\left\lfloor\frac{b}{c}\right\rfloor+\left\lfloor \dfrac{a\bmod c\times i+b\bmod c}{c}\right\rfloor\&=\left\lfloor\dfrac{a}{c}\right\rfloor\dfrac{n(n+1)}{2}+\left\lfloor\dfrac{b}{c}\right\rfloor(n+1)+f(a\bmod c,b\bmod c,c,n)
\end{aligned}
\]
\(a<c\)且\(b<c\)
把\(\left\lfloor \dfrac{ai+b}{c}\right\rfloor\)替换为\(\sum\limits_{j=0}\left[ j<\left\lfloor \dfrac{ai+b}{c}\right\rfloor\right]\)，其中\(j\)的上界为\(\left\lfloor \dfrac{an+b}{c}\right\rfloor-1\)。也就是求
\[f(a,b,c,n)=\sum_{i=0}^n\sum_{j=0}\left[j<\left\lfloor \dfrac{ai+b}{c}\right\rfloor\right]
\]
交换求和号
\[f(a,b,c,d)=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=0}^n\left[j<\left\lfloor\dfrac{ai+b}{c}\right\rfloor\right]\\]
乱搞一下后面那个东西，通过下取整与不等号的变换把\(i\)搞掉
\[j<\left\lfloor\dfrac{ai+b}{c}\right\rfloor \Leftrightarrow j+1\le \left\lfloor\dfrac{ai+b}{c}\right\rfloor\Leftrightarrow j+1\le \dfrac{ai+b}{c}\\Leftrightarrow \dfrac{cj+c-b}{a}\le i \Leftrightarrow i\ge \dfrac{cj+c-b}{a}\Leftrightarrow i>\left\lfloor\dfrac{cj+c-b-1}{a}\right\rfloor
\]
而\(i\)的上界是确定的，为\(n\)，也就是说\(j<\left\lfloor\dfrac{ai+b}{c}\right\rfloor\)的\(i\)的个数等于\(n-\left\lfloor\dfrac{cj+c-b-1}{a}\right\rfloor\)
\[\begin{aligned}
f(a,b,c,d)&=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=0}^n\left[j<\left\lfloor\dfrac{ai+b}{c}\right\rfloor\right]\&=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}n-\left\lfloor\dfrac{cj+c-b-1}{a}\right\rfloor\&= \left\lfloor\dfrac{an+b}{c}\right\rfloor n-\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\left\lfloor\dfrac{cj+c-b-1}{a}\right\rfloor\&= \left\lfloor\dfrac{an+b}{c}\right\rfloor n-f(c,c-b-1,a,\lfloor\frac{an+b}{c}\rfloor -1)
\end{aligned}
\]
（以后方便起见记\(\left\lfloor\dfrac{an+b}{c}\right\rfloor=m\)）
递归求解即可，边界为\(a=0\)
复杂度\(O(\log n)\)，证明类似欧几里得算法，故算法得名
类欧几里得算法
原文：https://www.cnblogs.com/harryzhr/p/14757802.html
