类欧几里得算法

这种东西。。。了解了解愉悦一下身心吧。只学了最简单的一种,其他的一坨扩展等哪天心情好了再看。

设$f(n, a, b, c) = \sum_{i=0}^n \lfloor \frac{ai + b}{c} \rfloor$

我们要计算的就是$f(n, a, b, c)$,如果认为$n, a, b, c$同阶的话,我们可以做到$\log n$的复杂度

前置知识

一些关于取整的小结论

$a < \lfloor \frac{b}{c} \rfloor \Leftrightarrow ac < b$

$a > \lceil \frac{b}{c} \rceil \Leftrightarrow ac > b$

$a \leqslant \lfloor \frac{b}{c} \rfloor \Leftrightarrow ac \leqslant b$

$a \geqslant \lceil \frac{b}{c} \rceil \Leftrightarrow ac \geqslant b$

$\lfloor \frac{b}{c} \rfloor = \lceil \frac{b-c+1}{c} \rceil$

$\lceil \frac{b}{c} \rceil = \lfloor \frac{b+c-1}{c} \rfloor$

然后就可以推柿子啦

神仙推导

然后就能递归算了,每次范围会至少折半,因此复杂度为$\log n$


一只菜鸡