类欧几里得算法

引入

设

原始文本

改写后的文本

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

这个式子看起来与我们之前见过的式子差别较大。含有向下取整操作的式子往往让人联想到数论分块方法。但另一方面，在这种情况下，数论分块方法似乎并不适用。不过我们确实可以尝试进行一些初步处理。

如果 a 或 b 不小于 c ，则可将 a,b 对 c 取模以简化运算：

f(a,b,c,n) = \sum_{i=0}^n [ai+b / c]

= (n(n+1)/2)[ a/c ] + (n+1)[ b/c ]

+f( a mod c, b mod c, n )

那么问题转化为满足a < c, b < c的情况。审视这个式子后会发现唯一的变量是i. 因此推导过程必须围绕变量i展开。在求解这个求和公式时通常采用的技术是关于条件与贡献的缩放与转换。具体而言，在函数\displaystyle f(a,b,c,n)=\sum_{i=0}^n\dfrac{\lfloor ai + b/c \r