类欧几里德算法

参考资料

• 类欧几里德算法 - 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$ 取模。