令 $ f(a,b,c,n) = \sum\limits_{i=0}^n \lfloor \dfrac{ai+b}{c} \rfloor $
$ f(a,b,c,n) = \sum\limits_{i=0}^n \lfloor \dfrac{(a \bmod c)i + (a- a \bmod c)i + (b \bmod c) + (b - b \bmod c)}{c} \rfloor $
$ = \sum\limits_{i=0}^n \lfloor \dfrac{(a \bmod c)i + (a- a \bmod c)i + (b \bmod c) + (b - b \bmod c)}{c} \rfloor $
其中 $ a-a \bmod c $ 和 $ b-b \bmod c $ 都是 $ c $ 的倍数，所以可以直接放到外面去。
$ = \sum\limits_{i=0}^n \lfloor \dfrac{(a \bmod c)i + (b \bmod c)}{c} \rfloor + \lfloor \dfrac{ai}{c} \rfloor + \lfloor \dfrac{b}{c} \rfloor $
后面这两个东西一个是常数，一个可以直接高斯求和，所以直接提到求和外面来。
$ = \dfrac{(n+1)\times n \times \lfloor \dfrac{a}{c} \rfloor}{2} + (n+1) \times \lfloor \dfrac{b}{c} \rfloor + \sum\limits_{i=0}^n \lfloor \dfrac{(a \bmod c)i + (b \bmod c)}{c} \rfloor $
即为：
$ = \dfrac{(n+1)\times n \times \lfloor \dfrac{a}{c} \rfloor}{2} + (n+1) \times \lfloor \dfrac{b}{c} \rfloor + f(a\bmod c,b\bmod c,c,n) $。
这样就把 $ a,b $ 的定义域缩小到了 $ [0,c) $，所以接下来考虑 $ a,b \in [0,c) $ 的情况。
（这里 $ a,b $ 为负数也可以做，在上面推导的时候把 $ \lfloor \dfrac{a}{c} \rfloor $ 替换为 $ \dfrac{a-a\bmod c}{c} $ 即可）
$ f(a,b,c,n) = \sum\limits_{i=0}^n \lfloor \dfrac{ai+b}{c} \rfloor $
$ = \sum\limits_{i=0}^n \sum\limits_{j=0}^{\lfloor \frac{ai+b}{c} \rfloor - 1} 1 $
$ = \sum\limits_{j=0}^{\lfloor \frac{an+b}{c} \rfloor - 1} \sum\limits_{i=0}^n [j<\lfloor \frac{ai+b}{c} \rfloor] $
考虑把艾弗森括号里面的东西提出来化简一下，
$ j<\lfloor \frac{ai+b}{c} \rfloor $
$ = j+1 \le \lfloor \frac{ai+b}{c} \rfloor $
$ = j+1 \le \frac{ai+b}{c} $
$ = cj+c \le ai+b $
$ = cj+c-b \le ai $
$ = cj+c-b-1 < ai $
$ = \lfloor \frac{cj+c-b-1}{a} \rfloor < i $
这样括号里面的东西就变成了对 $ i $ 的限制，且这个限制与后面这个求和无关。
所以后面这个求和就可以省去：
$ = \sum\limits_{j=0}^{\lfloor \frac{an+b}{c} \rfloor - 1} (n-\lfloor \frac{cj+c-b-1}{a} \rfloor) $
令 $ m=\lfloor \frac{an+b}{c} \rfloor $，则式子可以化为：
$ = m*n-\sum\limits_{i=0}^{m-1} \lfloor \frac{cj+c-b-1}{a} \rfloor $
注意到后面那个式子又可以变为 $ f $ 函数的形式，即 $ f(c,c-b-1,a,m-1) $。
即 $ f(a,b,c,n) = n*m - f(c,c-b-1,a,m-1) $。
这样就可以递归了，复杂度为 $ O(\log n) $。
那么总的递归式即可写成：
int calc(int a,int b,int c,int n) {if (a<0 or b<0) {int res=0;if (a<0) {int t=(a%c+c)%c;res-=(n+1)*n/2*((t-a)/c);a=t;}if (b<0) {int t=(b%c+c)%c;res-=(n+1)*((t-b)/c);b=t;}return res+calc(a,b,c,n);}if (a==0) return ((b/c)*(n+1));if (a>=c or b>=c) return (n+1)*n/2*(a/c)+(n+1)*(b/c)+calc(a%c,b%c,c,n);int m=(a*n+b)/c;return n*m-calc(c,c-b-1,a,m-1);
}
类欧模板剩下两个先咕咕咕