求$sum_{i=0}^{n} lfloor frac{a*i+b}{c} floor$
当$cleq a$或$c leq b$时
$$lfloor frac{a}{c} floor * frac{n*(n+1)}{2}+lfloor frac{b}{c} floor*(n+1)+sum_{i=0}^{n} lfloor frac{(a mod c) *i+(b mod c)}{c} floor$$
否则令$m=lfloor frac{a*i+b}{c} floor-1$
$$=sum_{i=0}^{n} sum_{j=0}^{m}1$$
$$=sum_{i=0}^{n} sum_{j=0}^{m} [j<lfloor frac{a*i+b}{c} floor]$$
$$=sum_{i=0}^{n} sum_{j=0}^{m} [j<lceil frac{a*i+b-c+1}{c} floor]$$
$$=sum_{i=0}^{n} sum_{j=0}^{m} [c*j < a*i+b-c+1]$$
$$=sum_{j=0}^{m} sum_{i=0}^{n} [a*i>c*j-b+c-1]$$
$$=sum_{j=0}^{m} sum_{i=0}^{n} [i>lfloor frac{c*j-b+c-1}{a} floor]$$
$$=sum_{j=0}^{m} n-lfloor frac{c*j-b+c-1}{a} floor$$
$$=n*(m+1)-sum_{j=0}^{m} lfloor frac{c*j-b+c-1}{a} floor$$
我们可以递归处理，复杂度和欧几里得算法相同。