类欧几里德算法

Summary

类欧几里德算法在对数时间内求形如 floor((ai+b)/c) 的取整求和，以及它与 i、i 的平方乘积的推广形式。它仿照辗转相除：当 a 不小于 c 或 b 不小于 c 时，先把商的整数部分提出以消去大系数；否则交换求和顺序，把对 i 的求和转成对取整值的求和，从而把问题递归规约到参数更小的同型子问题。参数每层按辗转相除下降，总递归层数为对数级。

参考资料

• 类欧几里德算法 - OI Wiki

简介

类欧几里德算法 在 $O(\log n)$ 内求形如 $\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor$ 的和式，以及它与 $i$、$i^2$ 乘积的推广。它仿照辗转相除：当 $a\ge c$ 或 $b\ge c$ 时先把整数部分提出，否则交换求和顺序，把问题递归地规约到参数更小的同型子问题。

例题

洛谷 P5170 【模板】类欧几里德算法

给定 $n,a,b,c$，求 $\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor$、$\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor^2$、$\sum_{i=0}^n i\lfloor\frac{ai+b}{c}\rfloor$ 对 $998244353$ 取模。