类欧几里得算法

问题引入

设

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

其中 \(a, b, c, n\) 是常数，需要 \(\mathcal O(\log n)\) 的做法。

若 \(a \geq c\) 或 \(b \geq c\)，我们可以将 \(a, b\) 对 \(c\) 取模以简化问题。

考虑到

\[x = \left \lfloor \frac{x}{c}\right \rfloor c + x \bmod c \]

故

\[\begin{split} f(a, b, c, n) &= \sum_{i=0}^n \left\lfloor\frac{ai + b}{c}\right\rfloor \\ &= \sum_{i=0}^n \left\lfloor\frac{(\left \lfloor \frac{a}{c}\right \rfloor c + a \bmod c)i + (\left \lfloor \frac{b}{c}\right \rfloor c + b \bmod c)}{c}\right\rfloor \\ &= \frac{n(n + 1)}{2} \left \lfloor \frac{a}{c}\right \rfloor + n \left \lfloor \frac{b}{c}\right \rfloor + f(a \bmod c , b\bmod c, c, n) \end{split} \]

此时一定有 \(a < c\) 且 \(b < c\)。

令

\[S(i)={\left\lfloor\frac{ai + b}{c}\right\rfloor} - 1 \]

再进行转化

\[\begin{split} \sum_{i=0}^n \left\lfloor\frac{ai + b}{c}\right\rfloor &= \sum_{i=0}^n \sum_{j=0}^{S(i)} 1 \\ &= \sum_{j=0}^{S(n)} \sum_{i=0}^n \left[ j \leq S(i) \right] \end{split} \]

考虑到

\[\begin{split} j \leq S(i) &\iff j + 1 \leq {\left\lfloor\frac{ai + b}{c}\right\rfloor} \\ j + 1 \leq {\left\lfloor\frac{ai + b}{c}\right\rfloor} &\iff j + 1 \leq \frac{ai + b}{c} \\ j + 1 \leq \frac{ai + b}{c} &\iff jc + c \leq ai + b \\ jc + c \leq ai + b &\iff jc + c - b \leq ai \\ jc + c - b \leq ai &\iff jc + c - b - 1 < ai \\ jc + c - b - 1 < ai &\iff \left \lfloor \frac{jc + c - b - 1}{a} \right \rfloor < i \end{split} \]

故

\[\begin {split} \sum_{j=0}^{S(n)} \sum_{i=0}^n \left[ j \leq S(i) \right] &= \sum_{j=0}^{S(n)} \sum_{i=0}^n \left[ i > \left \lfloor \frac{jc + c - b - 1}{a} \right \rfloor\right] \\ &= \sum_{j=0}^{S(n)} \left(n - \left \lfloor \frac{jc + c - b - 1}{a} \right \rfloor \right) \\ &= (S(n) + 1)n - \sum_{j=0}^{S(n)} \left \lfloor \frac{c j + (c - b - 1)}{a} \right \rfloor \\ &= (S(n) + 1)n - f(c, c - b - 1, a, S(n)) \end {split} \]

故

\[f(a, b, c, n) = (S(n) + 1)n - f(c, c - b - 1, a, S(n)) \]

可以发现，上述式子是一个递归式，我们不断重复上述过程，先取模，后递归，其实就是辗转相除的过程，时间复杂度 \(\mathcal O(\log n)\)。

拓展

我们再来推导两个变种求和式

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

推导 \(g\)

引理 1.

\[\sum_{i=0}^n i^2 = \frac{n (n+1)(2n+1)}{6} \]

证明如下：

考虑到

\[(n+1)^3=n^3+3n^2+3n+1 \]

故

\[\begin {split} (n+1)^3-n^3 &= 3n^2+3n+1 \\ n^3-(n-1)^3 &=3(n-1)^2+3(n-1)+1 \\ &\cdots \\ 2^3 - 1^3&=3 \times (2-1)^2+3 \times(2-1) + 1 \\ \end {split} \]

将这 \(n\) 个等式左右两边相加，得到

\[(n+1)^3 - 1 = 3(1^2 + 2^2 + \cdots n^2) + 3(1 + 2 + \cdots n) + n \]

即

\[n^3+3n^2+3n = 3(1^2 + 2^2 + \cdots n^2) + 3\frac{n(1 +n)}{2} + n \]

整理后得

\[\sum_{i=0}^n i^2 = \frac{n (n+1)(2n+1)}{6} \]

首先和 \(f\) 一样，对其取模（根据引理 1. 可将其展开）。

\[\begin{split} g(a, b, c, n) &= \sum_{i=0}^n i\left\lfloor\frac{ai + b}{c}\right\rfloor \\ &= \sum_{i=0}^n i\left\lfloor\frac{(\left \lfloor \frac{a}{c}\right \rfloor c + a \bmod c)i + (\left \lfloor \frac{b}{c}\right \rfloor c + b \bmod c)}{c}\right\rfloor \\ &= \frac{n(n + 1)(2n+1)}{6} \left \lfloor \frac{a}{c}\right \rfloor + \frac{n(n + 1)}{2} \left \lfloor \frac{b}{c}\right \rfloor + g(a \bmod c , b\bmod c, c, n) \end{split} \]

其他部分推导与 \(f\) 类似，有

\[\begin {split} g(a, b, c, n) &= \sum_{j=0}^{S(n)} \sum_{i=0}^n i\left[ j \leq S(i) \right] \\ &= \sum_{j=0}^{S(n)} \sum_{i=0}^n i\left[ i > \left \lfloor \frac{jc + c - b - 1}{a} \right \rfloor\right] \\ \end {split} \]

令

\[t =\left \lfloor \frac{jc + c - b - 1}{a} \right \rfloor \]

则有

\[\begin{split} g(a, b, c, n) &= \sum_{j=0}^{S(n)} \left((t + 1) + (t + 2) + \cdots + n\right) \\ &= \sum_{j=0}^{S(n)} \left(\frac{(t+1+n)\times(n-t)}{2}\right) \\ &= \frac{1}{2}\left[ (S(n) + 1) n(n+1) - \sum_{j=0}^{S(n)}t^2 - \sum_{j=0}^{S(n)}t\right] \\ &= \frac{1}{2} \left[(S(n) + 1) n(n+1) - h(c, c - b - 1, a, S(n)) - f(c, c - b - 1, a, S(n))\right] \end {split} \]

推导 \(h\)

咕咕咕。
同样套路，先取模

\[h(a, b, c, n) = \]

Luogu5170

Reference

OI-wiki