类欧几里得算法

令 $ 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);
}

类欧模板剩下两个先咕咕咕