概述
以求 $\sum_{i=1}^{n} \left \lfloor \frac{ai+b}{c} \right \rfloor$ 为例。此和式相当于求线段 $y=\frac{a}{c}x+\frac{b}{c}(x \in [1,n])$ 下面横坐标为正整数的整点个数。
考虑构造一个字符串，从左到右遍历该线段，每当遇到 $y=k(k \in \mathbb{Z})$ 则加 $\texttt{U}$，遇到 $x=k(k \in \mathbb{Z})$ 则加 $\texttt{R}$。只需要知道该字符串即可得到和式的和。
记 $f(S)$ 为字符串 $S$ 对应和式的答案，那么原和式的答案为 $f(\left \lfloor \frac{b}{c} \right \rfloor \times U + S)$。需要用 $f(S_1),f(S_2)$ 计算 $f(S_1+S_2)$，这个需要依据和式。来推一下我们的例子
用函数 $f$ 储存需要的信息，对于本例就是和式的值、$cnt(U)、cnt(R)$，那么定义的乘法就可以计算了。
记 $f(a,b,c,n,f_U,f_R)$，为将和式 $\sum_{i=1}^{n} \left \lfloor \frac{ai+b}{c} \right \rfloor$ 形成的字符串中的 $\texttt{U}$ 换成 $f_U$，$\texttt{R}$ 换成 $f_R$ 得到的连乘式的值。需要快速计算 $f(a,b,c,d,n,f_U,f_R)$。
将线段上下平移整数格是不改变函数的值的，所以
考虑对 $a,c$ 的大小分讨
$a \ge c$
$a < c$
需要将线段沿 $y=x$ 翻转，因为翻转后对于在线段上的顶点加入 $\texttt{U,R}$ 的顺序问题，还需要将线段向右平移 $\frac{1}{c}$，后面就是推式子了，懒得写了，抛出结论，记 $m = \left \lfloor \frac{an+b}{c} \right \rfloor$$m=0$
$m \ne 0$
计算时间复杂度，当 $a<c$ 时，有
最后得到 $T(a,c)=O(\log c)$。
例题
1.【模板】类欧几里得算法
考虑合并，记 $f,g,h$ 分别为 $\sum_{i=1}^{n} \left \lfloor \frac{ai+b}{c} \right \rfloor$，$\sum_{i=1}^{n} i\left \lfloor \frac{ai+b}{c} \right \rfloor$，$\sum_{i=1}^{n} \left \lfloor \frac{ai+b}{c} \right \rfloor^2$ 的值，$U,R$ 为 $\texttt{U,R}$ 的个数。
套用公式即可。
2.类欧几里得算法
二项式定理。