我们设 $f(a,b,c,n)=\sum_{i=0}^{n}\lfloor {\frac {ai+b} {c}} \rfloor$

其中 $a,b,c,n$ 为常数，我们需要一个 $O(logn)$ 的算法。

如果 $a≥c$ 或者 $b≥c$ ，我们可以将 $a,b$ 对 $c$ 取模来化简问题：

$f(a,b,c,n)=\sum_{i=0}^{n}\lfloor {\frac {ai+b} {c}} \rfloor$

$=\sum_{i=0}^{n}\lfloor {\frac {(\lfloor {\frac a c} \rfloor c+a\ mod\ c)i+(\lfloor {\frac b c} \rfloor c+b\ mod\ c)} {c}} \rfloor$

$={\frac {n(n+1)} {2}}\lfloor {\frac a c} \rfloor+(n+1)\lfloor {\frac b c} \rfloor+\sum_{i=0}^{n}\lfloor {\frac {(a\ mod\ c)i+(b\ mod\ c)} {c}} \rfloor$

$={\frac {n(n+1)} {2}}\lfloor {\frac a c} \rfloor+(n+1)\lfloor {\frac b c} \rfloor+f(a\ mod\ c,b\ mod\ c,c,n)$

这样我们就将前两个参数控制到一定比第三个参数小的形式了。

我们有 $\sum_{i=0}^{n}\lfloor {\frac {ai+b} {c}} \rfloor=\sum_{i=0}^{n}\sum_{j=0}^{\lfloor {\frac {ai+b} {c}} \rfloor-1}1$