类欧几里得算法
我们要求下面的函数：
[F(a,b,c,n)=sum_{i=0}^nlfloorfrac{a*i+b}{c}
floor
]
我们的方法是分两类情况递归下去求解。
边界条件：(a=0)是，(F=(n+1)lfloor frac{b}{c} floor)。
1.(ageq c)或(bgeq c)：
设：
[a=x*c+y
]
则：
[lfloorfrac{a}{c}
floor=lfloorfrac{y}{c}
floor+frac{x*c}{c}
]
通过这个公式我们可以得到如下的变换：
[egin{align}
lfloorfrac{a*i+b}{c}
floor&=lfloorfrac{(c*lfloorfrac{a}{c}
floor +amod c)*i+(c*lfloorfrac{b}{c}
floor + bmod c)}{c}
floor\
&=lfloorfrac{amod c*i+bmod c}{c}
floor +
i*lfloorfrac{a}{c}
floor
+lfloorfrac{b}{c}
floor \
end{align}
]
所以我们得到：
[F(a,b,c,n)=F(amod c,bmod c,c,n)+frac{n(n+1)}{2}lfloorfrac{a}{c}
floor+(n+1)lfloorfrac{b}{c}
floor
]
2.(a<c)且(b<c)：
首先我们要知道：(lfloor a floor)实际上就是(leq a)的正整数。
然后直接大力推式子：
设(m=lfloorfrac{a*n+b}{c} floor)
[egin{align}
F&=sum_{i=0}^nsum_{j=1}^m[lfloorfrac{a*i+b}{c}
floor geq j]\
&=sum_{i=0}^nsum_{j=0}^{m-1} [lfloorfrac{a*i+b}{c}
floor geq j+1]\
&=sum_{i=0}^nsum_{j=0}^{m-1}[frac{a*i+b}{c}geq j+1]\
&=sum_{j=0}^{m-1}sum_{i=0}^{n}[igeq frac{j*c+c-b}{a}]\
end{align}
]
因为：
[xgeq lfloor frac{a}{c}
floor\
Rightarrow x>lfloorfrac{a-1}{c}
floor
]
所以：
[egin{align}
F
&=sum_{j=0}^{m-1}sum_{i=0}^{n}[igeq 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-lfloorfrac{j*c+c-b-1}{a}
floor\
&=n*m-sum_{j=0}^{m-1}lfloorfrac{j*c+c-b-1}{a}
floor
end{align}
]
于是我们又得到了：
[F(a,b,c,n)=n*m-F(c,c-b-1,a,m-1)\
]
其他几种就不会了。