【类欧几里得算法】at_practice2_c
__vector__
·
·
算法·理论
省选前复习一下学过的算法。
考虑一个式子 f(a,b,c,n) = \sum\limits_{i=0}^n \lfloor \frac{ai+b}{c} \rfloor。
考虑拆分一下，能否把 a,b 取模 c：
$=\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)
如果 $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
考虑一下 $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)。
容易发现这个过程和欧几里得算法的复杂度一样。