类欧几里得算法
kkksx
·
·
个人记录
常用形式
洛谷模板
这里只解决第一个问，后面的类比第一个
求\sum_{i=0}^n \lfloor\frac{ai + b}{c} \rfloor,n \leq 10^9，多组询问
令f(n,a,b,c) = \sum_{i=0}^n \lfloor\frac{ai + b}{c} \rfloor，我们递归解决这个问题
$$f(n,a,b,c) = \sum_{i=0}^n \lfloor\frac{ai + b}{c} \rfloor$$
$$= \sum_{i=0}^n \lfloor\frac{i(a\%c) + b\%c}{c} \rfloor + i \lfloor \frac{a}{c} \rfloor + \lfloor \frac{b}{c} \rfloor$$
$$= f(n,a\%c,b\%c,c) + \frac{n(n + 1)}{2}\lfloor \frac{a}{c} \rfloor + (n + 1)\lfloor \frac{b}{c} \rfloor$$
$a<c\ \ \&\& \ \ b<c$ 时，令$m = \lfloor \frac{an + b}{c} \rfloor
f(n,a,b,c) = \sum_{i=0}^n \sum_{j = 1}^m [j \leq \lfloor \frac{ai + b}{c} \rfloor]
将枚举j放到外层，化简，有
=\sum_{j = 0}^{m-1}\sum_{i=0}^n[jc + c < ai + b + 1]
将限制j变成限制i
=\sum_{j = 0}^{m-1}\sum_{i=0}^n[i > \lfloor \frac{jc + c - b - 1}{a} \rfloor]
将大于号换成小于等于，即可递归下去
\sum_{j = 0}^{m-1}(n - [i \leq \lfloor \frac{jc + c - b - 1}{a} \rfloor]) = nm - f(m - 1,c,c-b-1,a)
递归边界为a = 0
时间复杂度为O(logn)
一般形式
LOJ138
求\sum_{i = 0}^n i^{k1} \lfloor \frac{ai + b}{c} \rfloor ^{k2},n\leq 10^9,k1,k2\leq 10
暂时不会，咕咕咕