类欧几里得

参考

引入

设

$f(a,b,c,n) = \sum_{i=0}^n \lfloor {\frac{ai+b}{c}}\rfloor$

其中$a,b,c,n$都是常数，需要一个$O(\log n)$的算法。

如果$a\ge c$或者$b\ge c$，可以将$a,b$对$c$取模以化简，即

$f(a,b,c,n) = \lfloor \frac{a}{c} \rfloor \frac{n(n+1)}{2} + \lfloor \frac{b}{c} \rfloor (n+1) + f(a\bmod c,b\bmod c,c,n)$

然后考虑$a<c,b<c$的情况：

$f(a,b,c,n) = \sum_{i=0}^n \lfloor {\frac{ai+b}{c}}\rfloor\\ = \sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{ai+b}{c} \rfloor - 1} 1\\ = \sum_{j=0}^{\lfloor \frac{an+b}{c} \rfloor - 1} \sum_{i=0}^n [j < \lfloor \frac{ai+b}{c} \rfloor]\\ = \sum_{j=0}^{\lfloor \frac{an+b}{c} \rfloor - 1} \sum_{i=0}^n [j < \frac{ai+b-c+1}{c}]\\ = \sum_{j=0}^{\lfloor \frac{an+b}{c} \rfloor - 1} \sum_{i=0}^n [\frac{jc-b + c - 1}{a} < i]\\ = \sum_{j=0}^{\lfloor \frac{an+b}{c} \rfloor - 1} n - \lfloor \frac{jc-b+c-1}{a}\rfloor\\ = \lfloor \frac{an+b}{c}\rfloor n - \sum_{j=0}^{\lfloor \frac{an+b}{c} \rfloor -1} \lfloor \frac{jc-b+c-1}{a}\rfloor\\ = \lfloor \frac{an+b}{c}\rfloor n - f(c,c-b-1,a,\lfloor \frac{an+b}{c}\rfloor -1)$

这样就又变成了$a\ge c$的问题，递归解决即可。复杂度为$O(\log n)$。

扩展

$g(a,b,c,n) = \sum_{i=0}^n i \lfloor \frac{ai+b}{c} \rfloor\\ h(a,b,c,n) = \sum_{i=0}^n \lfloor \frac{ai+b}{c} \rfloor ^2$

首先，让$a,b$对$c$取模。

$g(a,b,c,n) = g(a\bmod c, b\bmod c, c, n) + \lfloor\frac{a}{c}\rfloor \frac{n(n+1)(2n+1)}{6} + \lfloor \frac{b}{c} \rfloor \frac{n(n+1)}{2}\\ h(a,b,c,n) = h(a\bmod c, b\bmod c, c, n) + 2 \lfloor \frac{a}{c}\rfloor g(a\bmod c, b\bmod c, c, n) + 2\lfloor \frac{b}{c}\rfloor f(a\bmod c, b\bmod c, c, n)\\ +\lfloor \frac{a}{c} \rfloor^2 \frac{n(n+1)(2n+1)}{6}+2\lfloor\frac{a}{c}\rfloor \lfloor\frac{b}{c}\rfloor \frac{n(n+1)}{2} + \lfloor\frac{b}{c}\rfloor^2(n+1)$

然后进行类似的推导

$g(a,b,c,n) = \sum_{i=0}^n i \sum_{j=0}^{\lfloor \frac{ai+b}{c}\rfloor -1} 1\\ = \sum_{j=0}^{\lfloor \frac{an+b}{c} \rfloor - 1} \sum_{i=0}^n i [\frac{jc-b + c - 1}{a} < i]\\ = \sum_{j=0}^{\lfloor \frac{an+b}{c} \rfloor - 1} \frac{n(n+1)}{2} - \frac{1}{2}\lfloor \frac{jc-b+c-1}{a}\rfloor(\lfloor \frac{jc-b+c-1}{a}\rfloor + 1)\\ = \lfloor \frac{an+b}{c}\rfloor \frac{n(n+1)}{2} - {1\over 2}h(c,c-b-1,a,\lfloor \frac{an+b}{c}\rfloor -1) - {1\over 2}f(c,c-b-1,a,\lfloor \frac{an+b}{c}\rfloor -1)$ $h(a,b,c,n) = 2(\sum_{i=0}^n \sum_{j=0}^{\lfloor \frac{ai+b}{c}\rfloor -1} (j+1)) - f(a,b,c,n)\\$

考虑前面那部分

$= \sum_{j=0}^{\lfloor \frac{an+b}{c} \rfloor - 1} (j+1) \sum_{i=0}^n [\frac{jc-b + c - 1}{a} < i]\\ = \sum_{j=0}^{\lfloor \frac{an+b}{c} \rfloor - 1} (j+1)n - (j+1)\lfloor \frac{jc-b+c-1}{a}\rfloor\\ = \frac{1}{2}(\lfloor \frac{an+b}{c}\rfloor + 1)\lfloor \frac{an+b}{c}\rfloor n - g(c,c-b-1,a,\lfloor \frac{an+b}{c}\rfloor -1) - f(c,c-b-1,a,\lfloor \frac{an+b}{c}\rfloor -1)$

模板：luoguP5170