类欧几里得算法

数学 数论

---

类欧几里德算法 - OI Wiki

用途

计算函数求和, 形如

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

过程

当 $a \ge c$ 或 $b \ge c$ 时,

$$f(a,b,c,n)=\frac{n(n+1)}{2}*\lfloor \frac{a}{c} \rfloor + (n+1)* \lfloor \frac{b}{c} \rfloor + f(a \bmod c,b \bmod c,c,n).$$

当 $a < c$ 并且 $b < c$ 时,
设 $m=\lfloor \frac{an+b}{c} \rfloor,$

$$f(a,b,c,n)=mn-f(c,c-b-1,a,m-1).$$

递归处理直到 $a=0$ 即可.

例题

luoguP5171 Earthquake

数形结合, 把式子稍微转换一下, 套用类欧几里得算法即可.