我们设 $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$

然后我们交换和号：

$\sum_{j=0}^{\lfloor {\frac {an+b} {c}} \rfloor-1}\sum_{i=0}^{n}[j<\lfloor {\frac {ai+b} {c}} \rfloor]$

对于里面的式子，我们可以变换一下：

$j<\lfloor {\frac {ai+b} {c}} \rfloor \Leftrightarrow j+1≤ \lfloor {\frac {ai+b} {c}} \rfloor \Leftrightarrow j+1≤{\frac {ai+b} {c}} \Leftrightarrow jc+c≤ai+b \Leftrightarrow jc+c-b-1＜ai \Leftrightarrow \lfloor {\frac {jc+c-b-1} {a}} \rfloor ＜i$

这样我们设 $m= \lfloor {\frac {an+b} {c}} \rfloor$

原式变为： $f(a,b,c,n)=\sum_{j=0}^{m-1}\sum_{i=0}^{n}[i＞\lfloor {\frac {jc+c-b-1} {a}} \rfloor]=\sum_{j=0}^{m-1}(n-\lfloor {\frac {jc+c-b-1} {a}} \rfloor)=nm-f(c,c-b-1,a,m-1)$ 。然后第一个参数又比第三个大了，就一直取模这样，类似于求最大公约数。

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

\lfloor {\frac a c} \rfloor

1.求 $g(a,b,c,n)=\sum_{i=0}^{n}{\lfloor {\frac {ai+b} c} \rfloor}^{2}$ 和 $h(a,b,c,n)=\sum_{i=0}^{n}i \lfloor {\frac {ai+b} {c}} \rfloor$

当 $a==0$ 时， $g(a,b,c,n)=(n+1){\lfloor {\frac b c} \rfloor}^{2}$ ， ${\frac {n(n+1)} {2}}\lfloor {\frac b c} \rfloor$

当 $a≥c$ 或 $b≥c$ 时， $g(a,b,c,n)=\sum_{i=0}^{n}{( \lfloor {\frac {i(a\ mod\ c)+b\ mod\ c} {c}} \rfloor +i \lfloor {\frac a c} \rfloor + \lfloor {\frac b c} \rfloor)}^{2}$

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

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

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

$+{\frac {n(n+1)(2n+1)} 6}{\lfloor {\frac a c} \rfloor}^{2}+n(n+1)\lfloor {\frac a c} \rfloor \lfloor {\frac b c} \rfloor+(n+1){\lfloor {\frac b c} \rfloor}^{2}$

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

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

当 $a＜c$ 且 $b＜c$ 时，仍设 $m=\lfloor {\frac {an+b} c} \rfloor$

$g(a,b,c,n)=2\sum_{i=0}^{n}\sum_{j=1}^{\lfloor {\frac {ai+b} c} \rfloor}j-\sum_{i=0}^{n}\lfloor {\frac {ai+b} c} \rfloor$

$=-f(a,b,c,n)+2\sum_{i=0}^{n}\sum_{j=1}^{m}j[j≤{\lfloor {\frac {ai+b} c} \rfloor}]$