类欧几里德算法

引入

设

$$f(a,b,c,n)=\sum _{i=0}^n\lfloor \frac{ai+b}{c}\rfloor$$
考虑其几何意义，设$L:y=\frac{c}{ax+b}$
我们要求的实际上是二维平面上$L$，$x$轴，$y$轴和$x=n$这4条直线围成的梯形中整点的数量。细节地说，对于边界上的点，$x$轴上的点不能取，其他三条线上的点都能取。

其中 $a,b,c,n$ 是常数。需要一个 $O(\log n)$ 的算法。

这个式子和我们以前见过的式子都长得不太一样。带向下取整的式子容易让人想到数论分块，然而数论分块似乎不适用于这个求和。但是我们是可以做一些预处理的。

如果说 $a\ge c$ 或者 $b\ge c$，意味着可以将 $a,b$ 对 $c$ 取模以简化问题：
$$\begin{array}{rl}f(a,b,c,n)& =\sum _{i=0}^n\lfloor \frac{ai+b}{c}\rfloor \\ & =\sum _{i=0}^n\lfloor \frac{\left(\lfloor \frac{a}{c}\rfloor c+a\mathrm{m}\mathrm{o}\mathrm{d}c\right)i+\left(\lfloor \frac{b}{c}\rfloor c+b\mathrm{m}\mathrm{o}\mathrm{d}c\right)}{c}\rfloor \\ & =\frac{n(n+1)}{2}\lfloor \frac{a}{c}\rfloor +(n+1)\lfloor \frac{b}{c}\rfloor +\sum _{i=0}^n\lfloor \frac{\left(a\mathrm{m}\mathrm{o}\mathrm{d}c\right)i+\left(b\mathrm{m}\mathrm{o}\mathrm{d}c\right)}{c}\rfloor \\ & =\frac{n(n+1)}{2}\lfloor \frac{a}{c}\rfloor +(n+1)\lfloor \frac{b}{c}\rfloor +f(a\mathrm{m}\mathrm{o}\mathrm{d}c,b\mathrm{m}\mathrm{o}\mathrm{d}c,c,n)\end{array}$$

那么问题转化为了 $a<c,b<c$ 的情况。观察式子，你发现只有 $i$ 这一个变量。因此要推就只能从 $i$ 下手。在推求和式子中有一个常见的技巧，就是条件与贡献的放缩与转化。具体地说，在原式 $f(a,b,c,n)=\sum _{i=0}^n\lfloor \frac{ai+b}{c}\rfloor$ 中，$0\le i\le n$ 是条件，而 $\lfloor \frac{ai+b}{c}\rfloor$ 是对总和的贡献。

要加快一个和式的计算过程，所有的方法都可以归约为 贡献合并计算。但你发现这个式子的贡献难以合并，怎么办？将贡献与条件做转化 得到另一个形式的和式。具体地，我们直接把原式的贡献变成条件：

$$\sum _{i=0}^n\lfloor \frac{ai+b}{c}$$