类欧几里得算法
我们要求下面的函数：
\[
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\)：
首先我们有如下的变换：
\[
\begin{align}
\lfloor\frac{a*i+b}{c} \rfloor&=\lfloor\frac{a*i+b\bmod c}{c} \rfloor
+\lfloor\frac{b}{c} \rfloor \\
&=\lfloor\frac{(a*i) \bmod c+b\bmod c}{c} \rfloor +\lfloor\frac{a*i}{c} \rfloor
+\lfloor\frac{b}{c} \rfloor \\
&=\lfloor\frac{(a\bmod c*i)\bmod c+b\bmod c}{c} \rfloor +i*\lfloor\frac{a}{c}\rfloor+\lfloor\frac{a\bmod c*i}{c} \rfloor
+\lfloor\frac{b}{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}
\]
设：
\[
a=x*c+y
\]
则：
\[
\lfloor\frac{a}{c} \rfloor=\lfloor\frac{y}{c}\rfloor+\frac{x*c}{c}
\]
这些公式都可以用这个公式来证明（或者感性理解）。
所以我们得到：
\[
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)\\
\]其他几种就不会了。