类欧几里得
这里只是类欧几里得的一种：
快速求下式： \[f(a, b, c, n) = \sum_{i=0}^n
\lfloor \frac{ai+b}{c} \rfloor\]
其中 a, b, c, n 都是正整数。
缩小 a, b 规模
首先的目标是让 a, b 小于 c 。
结论 1 ：
\[\lfloor \frac{Ax+B}{y} \rfloor =
\lfloor \frac{A(x\%y)+B}{y} \rfloor + A\lfloor \frac{x}{y}
\rfloor\]
证明：
首先用到整除与取模的转换： \(\lfloor
\frac{x}{y} \rfloor = \frac{x-x\%y}{y}\) 。
得到原命题等价于：
\[\frac{Ax+B-(Ax+B)\%y}{y} =
\frac{A(x\%y)+B-(Ax+B)\%y}{y} + A\frac{x-x\%y}{y}\] \[Ax + B - (Ax+B)\%y = A(x\%y) + B - (Ax+B)\%y +
A(x-x\%y)\] \[Ax - (Ax+B)\%y = A(x\%y)
- (Ax+B)\%y + A(x-x\%y)\] \[Ax =
A(x\%y) + A(x-x\%y)\] \[Ax = A(x\%y) +
Ax - A(x\%y)\]
得证。
那么通过这个结论可以得知：
\[
\begin{equation}
\begin{aligned}
f(a, b, c, n) &= \sum_{i=0}^n \lfloor \frac{ai+b}{c} \rfloor \\\\
&= \sum_{i=0}^n (\lfloor \frac{(a\%c)i+b\%c}{c} \rfloor +
i\lfloor \frac{a}{c} \rfloor + \lfloor \frac{b}{c} \rfloor) \\\\
&= f(a\%c, b\%c, c, n) + \sum_{i=0}^n (
i\lfloor \frac{a}{c} \rfloor + \lfloor \frac{b}{c} \rfloor) \\\\
\end{aligned}
\end{equation}
\]
后面那一段就是一个等差数列求和，于是 a, b 被转换为小于 c 。
转换成子问题减小规模
整除除了用取模代替外，还有一种方法。
结论 2 ：
\[\lfloor \frac{x}{y} \rfloor =
\sum_{i=1}^{MAX} [i \leq \frac{x}{y}]\]
其中 MAX 是任意一个足够大的值。
证明？相当于从 1 开始数，感性理解即可。
那么通过这个结论可以得知：
\[
\begin{equation}
\begin{aligned}
f(a, b, c, n) &= \sum_{i=0}^n \lfloor \frac{ai+b}{c} \rfloor \\\\
&= \sum_{i=0}^n \sum_{j=1}^{(an+b)/c} [j \leq \frac{ai+b}{c}] \\\\
&= \sum_{i=0}^n \sum_{j=0}^{(an+b)/c-1} [j + 1 \leq \frac{ai+b}{c}]
\\\\
&= \sum_{i=0}^n \sum_{j=0}^{(an+b)/c-1} [cj + c \leq ai+b] \\\\
&= \sum_{i=0}^n \sum_{j=0}^{(an+b)/c-1} [cj + c - 1 < ai+b] \\\\
&= \sum_{i=0}^n \sum_{j=0}^{(an+b)/c-1} [\frac{cj+c-b-1}{a} < i]
\\\\
&= \sum_{j=0}^{(an+b)/c-1} \sum_{i=0}^n [\frac{cj+c-b-1}{a} < i]
\\\\
&= \sum_{j=0}^{(an+b)/c-1}
(n + 1 - \sum_{i=0}^n [i \leq \frac{cj+c-b-1}{a}]) \\\\
&= \sum_{j=0}^{(an+b)/c-1}
(n - \lfloor \frac{cj+c-b-1}{a} \rfloor) \\\\
&= n \lfloor \frac{an+b}{c} \rfloor -
\sum_{j=0}^{(an+b)/c-1} (\lfloor \frac{cj+c-b-1}{a} \rfloor) \\\\
&= n \lfloor \frac{an+b}{c} \rfloor - f(c, c-b-1, a, (an+b)/c-1)
\end{aligned}
\end{equation}
\]
那么就得到了一个递归计算 f(a, b, c, n) 的算法，
a = 0 时上式不成立，因为上面的推导有除以 a 的步骤。
因此将 a = 0 作为终止状态，此时 f 的计算是常数数列求和。
复杂度是对数复杂度 log(a)，因为上面的过程规模的减小速度相当于 gcd 。
数形结合
复习的时候看到这么多式子头都大了，但是这个类欧事实上就是数一个三角形内的整点数，第一步很好理解，第二步本质上就是把坐标轴翻转了一下然后用一个正方形的点数减去一个三角形的点数（事实上可以不用这个补集转换），很快就可以得到同样的结论，可以避免冗长的纯式子推导。
放在二维平面上，第一步的本质就是把斜率固定在小于 1 的数，第二步的本质就是翻转坐标轴，翻转后斜率会变为原来的倒数，于是会超过 1 。这样反复进行就可以逐渐数完三角形内的所有整点。
UPD: 准确来说不是三角形，是梯形，但显然两者可以相互转换。
但是更复杂的类欧这个数形结合好像就不管用了，还是得用数学推导。