类欧几里得算法

我们要求下面的函数：

\[ F(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{a*i+b}{c}\rfloor \]

我们的方法是分两类情况递归下去求解。

边界条件：\(a=0\)是，\(F=(n+1)\lfloor \frac{b}{c} \rfloor\)。

1.\(a\geq c\)或\(b\geq c\)：

设：

\[ a=x*c+y \]

则：

\[ \lfloor\frac{a}{c} \rfloor=\lfloor\frac{y}{c}\rfloor+\frac{x*c}{c} \]

通过这个公式我们可以得到如下的变换：

\[ \begin{align} \lfloor\frac{a*i+b}{c} \rfloor&=\lfloor\frac{(c*\lfloor\frac{a}{c} \rfloor +a\bmod c)*i+(c*\lfloor\frac{b}{c} \rfloor + b\bmod c)}{c} \rfloor\\ &=\lfloor\frac{a\bmod c*i+b\bmod c}{c} \rfloor + i*\lfloor\frac{a}{c}\rfloor +\lfloor\frac{b}{c} \rfloor \\ \end{align} \]

所以我们得到：

\[ F(a,b,c,n)=F(a\bmod c,b\bmod c,c,n)+\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor \]

2.\(a<c\)且\(b<c\)：

首先我们要知道：\(\lfloor a\rfloor\)实际上就是\(\leq a\)的正整数。

然后直接大力推式子：

设\(m=\lfloor\frac{a*n+b}{c} \rfloor\)

\[ \begin{align} F&=\sum_{i=0}^n\sum_{j=1}^m[\lfloor\frac{a*i+b}{c} \rfloor \geq j]\\ &=\sum_{i=0}^n\sum_{j=0}^{m-1} [\lfloor\frac{a*i+b}{c} \rfloor \geq j+1]\\ &=\sum_{i=0}^n\sum_{j=0}^{m-1}[\frac{a*i+b}{c}\geq j+1]\\ &=\sum_{j=0}^{m-1}\sum_{i=0}^{n}[i\geq \frac{j*c+c-b}{a}]\\ \end{align} \]

因为：

\[ x\geq \lfloor \frac{a}{c} \rfloor\\ \Rightarrow x>\lfloor\frac{a-1}{c}\rfloor \]

所以：

\[ \begin{align} F &=\sum_{j=0}^{m-1}\sum_{i=0}^{n}[i\geq \frac{j*c+c-b}{a}]\\ &=\sum_{j=0}^{m-1}\sum_{i=0}^{n}[i> \frac{j*c+c-b-1}{a}]\\ &=\sum_{j=0}^{m-1}n-\lfloor\frac{j*c+c-b-1}{a} \rfloor\\ &=n*m-\sum_{j=0}^{m-1}\lfloor\frac{j*c+c-b-1}{a} \rfloor \end{align} \]

于是我们又得到了：

\[ F(a,b,c,n)=n*m-F(c,c-b-1,a,m-1)\\ \]

其他几种就不会了。