类欧几里得算法
定义
\[\displaystyle\begin{aligned} f(a,b,c,n) &= \sum\limits_{i = 0}^{n}\left\lfloor\dfrac{ai + b}{c}\right\rfloor \\ g(a,b,c,n) &= \sum\limits_{i = 0}^{n}{\left\lfloor\dfrac{ai + b}{c}\right\rfloor}^2 \\ h(a,b,c,n) &= \sum\limits_{i = 0}^{n}i\left\lfloor\dfrac{ai + b}{c}\right\rfloor \end{aligned}\]给定 \(n,a,b,c\)，求 \(f(a,b,c,n),g(a,b,c,n),h(a,b,c,n)\)，对 \(998244353\) 取模（\(1 \le T \le 10^5,0 \le n,a,b,c \le 10^9, c \neq 0\)）。
考虑函数 \(f\)。首先考虑 \(a > c \lor b > c\) 的情况
\[\displaystyle \begin{aligned} f(a,b,c,n) &= \sum\limits_{i = 0}^{n}\left\lfloor\dfrac{ai + b}{c}\right\rfloor \\ &= \sum\limits_{i = 0}^{n}\left\lfloor\dfrac{{(\left\lfloor\dfrac{a}{c}\right\rfloor c + a \bmod c)i + \left\lfloor\dfrac{b}{c}\right\rfloor c + b \bmod c}}{c}\right\rfloor \\ &= \sum\limits_{i = 0}^{n}(\left\lfloor\dfrac{a}{c}\right\rfloor i + \left\lfloor\dfrac{b}{c}\right\rfloor + \left\lfloor\dfrac{(a \bmod c) i + (b \bmod c)}{c}\right\rfloor) \\ &= \dfrac{n(n + 1)}{2}\left\lfloor\dfrac{a}{c}\right\rfloor + (n + 1)\left\lfloor\dfrac{b}{c}\right\rfloor + \sum\limits_{i = 0}^{n}\left\lfloor\dfrac{{a \bmod ci + b \bmod c}}{c}\right\rfloor \\ &= \dfrac{n(n + 1)}{2}\left\lfloor\dfrac{a}{c}\right\rfloor + (n + 1)\left\lfloor\dfrac{b}{c}\right\rfloor + f(a \bmod c,b \bmod c, c, n) \\ \end{aligned}\]接下来考虑 \(a \le c \land b \le c\) 的情况
\[\displaystyle \begin{aligned} f(a,b,c,n) &= \sum\limits_{i = 0}^{n}\left\lfloor\dfrac{ai + b}{c}\right\rfloor \\ &= \sum\limits_{i = 0}^{n}\sum\limits_{j = 0}^{\left\lfloor\frac{ai + b}{c}\right\rfloor - 1}1 \\ &= \sum\limits_{j}\sum\limits_{i = 0}^{n}{\left[j < \left\lfloor\frac{ai + b}{c}\right\rfloor \right]} \\ &= \sum\limits_{j = 0}^{\left\lfloor\frac{an + b}{c}\right\rfloor - 1}\sum\limits_{i = 0}^{n}{\left[j < \left\lfloor\frac{ai + b}{c}\right\rfloor \right]} \\ \end{aligned}\]考虑限制条件 \(j < \left\lfloor\frac{ai + b}{c}\right\rfloor\)
\[\displaystyle \begin{aligned} j < \left\lfloor\frac{ai + b}{c}\right\rfloor & \Leftrightarrow j < \frac{ai + b}{c} \\ & \Leftrightarrow j + 1 \le \frac{ai + b}{c} \\ & \Leftrightarrow jc + c \le ai + b \\ & \Leftrightarrow jc + c - b \le ai \\ & \Leftrightarrow jc + c - b - 1 < ai \\ & \Leftrightarrow \dfrac{jc + c - b - 1}{a} < i \\ & \Leftrightarrow \left\lfloor\dfrac{jc + c - b - 1}{a}\right\rfloor < i \end{aligned}\]记 \(\displaystyle m = \left\lfloor\frac{an + b}{c}\right\rfloor,t = \left\lfloor\dfrac{jc + c - b - 1}{a}\right\rfloor\)，则
\[\displaystyle \begin{aligned} f(a,b,c,n) &= \sum\limits_{j = 0}^{\left\lfloor\frac{an + b}{c}\right\rfloor - 1}\sum\limits_{i = 0}^{n}{\left[j < \left\lfloor\frac{ai + b}{c}\right\rfloor \right]} \\ &= \sum\limits_{j = 0}^{m - 1}\sum\limits_{i = 0}^{n}{\left[i > t\right]} \\ &= \sum\limits_{j = 0}^{m - 1}(n - t) \\ &= nm - \sum\limits_{j = 0}^{m - 1}\left\lfloor\dfrac{jc + c - b - 1}{a}\right\rfloor \\ &= nm - f(c,c - b - 1, a, m - 1) \end{aligned}\]观察到当 \(a > c\) 时，\(a \rightarrow a \bmod c\)；当 \(a \le c\) 时，\(a,c\) 互换位置，故复杂度为 \(\mathcal{O}(\log\max(a,c))\)。
考虑函数 \(g\)。首先考虑 \(a > c \lor b > c\) 的情况
\[\displaystyle \begin{aligned} g(a,b,c,n) &= \sum\limits_{i = 0}^{n}{\left\lfloor\dfrac{ai + b}{c}\right\rfloor}^2 \\ &= \sum\limits_{i = 0}^{n}{\left\lfloor\dfrac{{(\left\lfloor\dfrac{a}{c}\right\rfloor c + a \bmod c)i + \left\lfloor\dfrac{b}{c}\right\rfloor c + b \bmod c}}{c}\right\rfloor}^2 \\ &= \sum\limits_{i = 0}^{n}(\left\lfloor\dfrac{a}{c}\right\rfloor i + \left\lfloor\dfrac{b}{c}\right\rfloor + \left\lfloor\dfrac{(a \bmod c) i + (b \bmod c)}{c}\right\rfloor)^2 \\ &= \dfrac{n(n + 1)(2n + 1)}{6}\left\lfloor\dfrac{a}{c}\right\rfloor^2 + \dfrac{n(n + 1)}{2}\left\lfloor\dfrac{b}{c}\right\rfloor^2 + g(a \bmod c,b \bmod c, c, n) \\ &+ \dfrac{n(n + 1)}{2}\left\lfloor\dfrac{a}{c}\right\rfloor\left\lfloor\dfrac{b}{c}\right\rfloor+ 2 \left\lfloor\dfrac{a}{c}\right\rfloor h(a \bmod c,b \bmod c, c, n) + 2 \left\lfloor\dfrac{b}{c}\right\rfloor f(a \bmod c,b \bmod c, c, n) \end{aligned}\]接下来考虑 \(a \le c \land b \le c\) 的情况，观察到
\[n^2 = 2\dfrac{n(n + 1)}{2} - n = 2\left(\sum_{i = 1}^{n}i\right) - n \]那么
\[\displaystyle \begin{aligned} g(a,b,c,n) &= \sum\limits_{i = 0}^{n}{\left\lfloor\dfrac{ai + b}{c}\right\rfloor}^2 \\ &= \sum\limits_{i = 0}^{n}\left[2\left(\sum\limits_{j=1}^{\left\lfloor\frac{ai + b}{c}\right\rfloor}j\right) - {\left\lfloor\frac{ai + b}{c}\right\rfloor} \right] \\ \end{aligned}\]考虑处理 \(\displaystyle \sum\limits_{i = 0}^{n}\sum\limits_{j=1}^{\left\lfloor\frac{ai + b}{c}\right\rfloor}j\)，记 \(\displaystyle m = \left\lfloor\frac{an + b}{c}\right\rfloor,t = \left\lfloor\dfrac{jc + c - b - 1}{a}\right\rfloor\)
\[\displaystyle \begin{aligned} & \sum\limits_{i = 0}^{n}\sum\limits_{j=1}^{\left\lfloor\frac{ai + b}{c}\right\rfloor}j \\ =& \sum\limits_{i = 0}^{n}\sum\limits_{j=0}^{\left\lfloor\frac{ai + b}{c}\right\rfloor - 1}\left(j + 1\right) \\ =& \sum\limits_{j = 0}^{m - 1}\left(j + 1\right)\sum\limits_{i = 0}^{n}\left[i > t\right] \\ =& \sum\limits_{j = 0}^{m - 1}\left(j + 1\right)\left(n - t\right) \\ =& \dfrac{1}{2}nm(m + 1) + h(c,c - b - 1,a,m - 1) - f(c,c - b - 1,a,m - 1) \end{aligned}\]那么
\[\displaystyle \begin{aligned} g(a,b,c,n) &= \sum\limits_{i = 0}^{n}\left[2\left(\sum\limits_{j=1}^{\left\lfloor\frac{ai + b}{c}\right\rfloor}j\right) - {\left\lfloor\frac{ai + b}{c}\right\rfloor} \right] \\ &= nm(m + 1) + 2h(c,c - b - 1,a,m - 1) - 2f(c,c - b - 1,a,m - 1) + f(a,b,c,n) \end{aligned}\]考虑函数 \(h\)。首先考虑 \(a > c \lor b > c\) 的情况
\[\displaystyle \begin{aligned} h(a,b,c,n) &= \sum\limits_{i = 0}^{n}i\left\lfloor\dfrac{ai + b}{c}\right\rfloor \\ &= \sum\limits_{i = 0}^{n}i\left\lfloor\dfrac{{(\left\lfloor\dfrac{a}{c}\right\rfloor c + a \bmod c)i + \left\lfloor\dfrac{b}{c}\right\rfloor c + b \bmod c}}{c}\right\rfloor \\ &= \sum\limits_{i = 0}^{n}i(\left\lfloor\dfrac{a}{c}\right\rfloor i + \left\lfloor\dfrac{b}{c}\right\rfloor + \left\lfloor\dfrac{(a \bmod c) i + (b \bmod c)}{c}\right\rfloor) \\ &= \dfrac{n(n + 1)(2n + 1)}{6}\left\lfloor\dfrac{a}{c}\right\rfloor + \dfrac{n(n + 1)}{2}\left\lfloor\dfrac{b}{c}\right\rfloor + \sum\limits_{i = 0}^{n}i\left\lfloor\dfrac{{a \bmod ci + b \bmod c}}{c}\right\rfloor \\ &= \dfrac{n(n + 1)(2n + 1)}{6}\left\lfloor\dfrac{a}{c}\right\rfloor + \dfrac{n(n + 1)}{2}\left\lfloor\dfrac{b}{c}\right\rfloor + h(a \bmod c,b \bmod c, c, n) \\ \end{aligned}\]接下来考虑 \(a \le c \land b \le c\) 的情况，记 \(\displaystyle m = \left\lfloor\frac{an + b}{c}\right\rfloor,t = \left\lfloor\dfrac{jc + c - b - 1}{a}\right\rfloor\)
\[\displaystyle \begin{aligned} h(a,b,c,n) &= \sum\limits_{i = 0}^{n}i\left\lfloor\dfrac{ai + b}{c}\right\rfloor \\ &= \sum\limits_{j = 0}^{m - 1}\sum_{i = 0}^{n}\left[i > t\right]i \\ &= \sum\limits_{j = 0}^{m - 1}\dfrac{(n + t + 1)(n - t)}{2} \\ &= \dfrac{1}{2}\left[mn(n + 1) - \sum\limits_{i = 0}^{n}t^2 - \sum\limits_{i = 0}^{n}t\right] \\ &= \dfrac{1}{2}\left[mn(n + 1) - g(c,c - b - 1,a,m - 1) - f(c,c - b - 1,a,m - 1)\right] \\ \end{aligned}\] 标签：lfloor,right,dfrac,欧几里得,rfloor,算法,sum,left From： https://www.cnblogs.com/User-Unauthorized/p/euclidean.html