本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-16 15:28:04

省选前复习一下学过的算法。

考虑一个式子 $f(a,b,c,n) = \sum\limits_{i=0}^n \lfloor \frac{ai+b}{c} \rfloor$。

考虑拆分一下，能否把 $a,b$ 取模 $c$：
$f(a,b,c,n) = \sum\limits_{i=0}^n \lfloor \frac{\lfloor \frac{a}{c}\rfloor ci+i(a \bmod c)+\lfloor \frac{b}{c}\rfloor c +b \bmod c}{c}\rfloor$。
$=\sum\limits_{i=0}^n \lfloor \frac{(a\bmod c)i+\lfloor \frac{b}{c}\rfloor}{c}\rfloor + \lfloor \frac{a}{c}\rfloor(\sum\limits_{i=1}^n i)+(n+1)(b \bmod c)$
$= f(a \bmod c,b \bmod c,c,n) + \lfloor \frac{a}{c} \rfloor \frac{(1+n)n}{2}+(n+1)(b \bmod c)$.

如果 $a \ge c \lor b \ge c$，那么直接递归。

否则，需要找到其他办法减小这个问题的规模。

简单变形一下。

$f(a,b,c,n) = \sum\limits_{i=0}^n \sum\limits_{j = 0}^{\lfloor \frac{ai+b}{c}\rfloor-1}1 $
$= \sum\limits_{j=0}^{\lfloor {\frac{ai+b}{c}}\rfloor-1}\sum\limits_{i=0}^n [\lfloor\frac{ai+b}{c}\rfloor \ge j]$.

考虑一下 $i,j$ 的大小关系。

$j \le \lfloor\frac{ai+b}{c}\rfloor-1$
$j \le \frac{ai+b}{c}-1$
$ai+b \ge jc+c$
$ai \ge jc+c-b$
$a \gt \frac{jc+c-b-1}{i}$

$f(a,b,c,n) = \sum\limits_{j=0}^{\lfloor \frac{an+b}{c}\rfloor-1}(n-\lfloor\frac{cj+c-b-1}{a}\rfloor)$
令 $T = \lfloor \frac{an+b}{c}\rfloor-1$。
原式转化为 $(T+1)n-f(c,c-b-1,a,T)$。

容易发现这个过程和欧几里得算法的复杂度一样。