类欧几里得算法

标签：lfloor right frac 欧几里得 rfloor 算法 sum left

要求类似于这样的东西：

\[\begin{align*} f(n,a,b,c)&=\sum\limits_{i=0}^n {\left\lfloor \frac{ai+b}{c} \right\rfloor} \\ g(n,a,b,c)&= \sum\limits_{i=0}^n {\left\lfloor \frac{ai+b}{c} \right\rfloor}^2 \\ h(n,a,b,c)&= \sum\limits_{i=0}^n {i\left\lfloor \frac{ai+b}{c} \right\rfloor} \\ &\text{等等} \end{align*} \]

有一些关于取整不等式的前置知识：

\[(a\in\mathbb{Z},b\in\mathbb{R})\ \ a<\left\lfloor b \right\rfloor \Leftrightarrow a+1 \le\left\lfloor b \right\rfloor \Leftrightarrow a+1 \le b \]

\[(a\in\mathbb{R},b\in\mathbb{Z})\ \ \left\lfloor a \right\rfloor < b \Leftrightarrow a < b \]

\[(a\in\mathbb{Z},b\in\mathbb{Z})\ \ a \le b \Leftrightarrow a<b+1 \Leftrightarrow a-1<b \]

\[(a \in \mathbb{R},b \in \mathbb{Z})\left\lfloor a \right\rfloor=b+\left\lfloor a-b \right\rfloor \]

然后分析问题。

\[\sum\limits_{i=0}^{n}\left\lfloor \frac{ai+b}{c} \right\rfloor = \sum\limits_{i=0}^{n} \left\lfloor \left\lfloor \frac{a}{c} \right \rfloor i+ \left\lfloor \frac{b}{c} \right \rfloor + \frac{(a \bmod c)i+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 + \sum\limits_{i=0}^{n} \left\lfloor \frac{(a \bmod c)i+b \bmod c}{c} \right\rfloor\]

我们仍然设结果为 \(f(n,a,b,c)\)，但此时 \(a,b<c\)。
并且，此时我们设 \(m_i=\left\lfloor \frac{ai+b}{c} \right\rfloor\)
于是

\[\sum\limits_{i=0}^n m_i = \sum\limits_{i=0}^{n} \sum\limits_{j=0}^{m_i-1} 1 = \sum\limits_{j=0}^{m_n-1} \sum\limits_{i=0}^{n} [j<m_i] \]

使用引理，

\[j < m_i \Leftrightarrow j+1 \le \frac{ai+b}{c} \Leftrightarrow \frac{jc+c-b-1}{a} < i \]

于是

\[f(n,a,b,c)=\sum\limits_{j=0}^{m_n-1}(n-\left\lfloor \frac{jc+c+b-1}{a} \right\rfloor)=nm-f(m_n-1,c,c-b-1,a) \]

边界为 \(m_n=0\)
类似于欧几里得算法（辗转相除），时间复杂度 \(O(\log n)\)

标签：lfloor,right,frac,欧几里得,rfloor,算法,sum,left
From： https://www.cnblogs.com/hbhz-zcy/p/18029073