类欧几里得算法

求 $\sum _{i=0}^n\lfloor \frac{ai+b}{c}\rfloor$

推式子步骤：

分类讨论

$a=0$

是个最简式子

$b\ge c$ 或 $a\ge c$

由 $f(a\mathrm{mod}c,b\mathrm{mod}c,c,n)$ 转移过来，拆一下括号就行

其他情况

设$M=\lfloor \frac{an+b}{c}\rfloor$

$\lfloor \frac{ai+b}{c}\rfloor ={\sum }_{j=1}^M[j\le \lfloor \frac{ai+b}{c}\rfloor ]$

1. 拆一下后面的除号
2. 把所有 $j$ 变成 $j-1$
3. 交换求和顺序
4. 变成 $i>x$ 的形式
5. 变成 $n-i\le x$ 的形式
6. 后面直接换成 $f(c,c-b-1,a,m-1)$

int floor_sum(int n, int c, int a, int b) {
	if(a==0) return (n+1)*(b/c); 
	if(a>=c || b>=c) 
		return floor_sum(n, c, a%c, b%c)+n*(n+1)/2*(a/c)+(n+1)*(b/c); 
	int m=(a*n+b)/c; 
	return n*m-floor_sum(m-1, a, c, c-b-1); 
}
1
2
3
4
5
6
7

对于 $\sum _{i=0}^n{\lfloor \frac{ai+b}{c}\rfloor }^2,\sum _{i=0}^{n}i\lfloor \frac{ai+b}{c}\rfloor$ 的求解

推的方法类似，不过会互相调用

node floor_sum(int a, int b, int c, int n) {
	if(a==0) return {(n+1)*(b/c)%p, (n+1)*(b/c)%p*(b/c)%p, n*(n+1)%p*i2%p*(b/c)%p}; 
	if(a>=c || b>=c) {
		node t=floor_sum(a%c, b%c, c, n); 
		int F=t.f+n*(n+1)%p*i2%p*(a/c)%p+(n+1)*(b/c)%p; 
		int G=t.g+2*t.h%p*(a/c)%p+2*(b/c)%p*t.f%p+n*(n+1)%p*(2*n+1)%p*i6%p*(a/c)%p*(a/c)%p+(n+1)*n%p*(a/c)%p*(b/c)%p+(n+1)*(b/c)%p*(b/c)%p; 
		int H=t.h+n*(n+1)%p*(2*n+1)%p*i6%p*(a/c)%p+n*(n+1)%p*i2%p*(b/c)%p; 
		return {F%p, G%p, H%p}; 
	}
	int m=(a*n+b)/c; 
	node t=floor_sum(c, c-b-1, a, m-1); 
	int F=n*m%p-t.f; 
	int G=n*m%p*(m+1)%p-2*t.f%p-2*t.h%p-F; 
	int H=(m*n%p*(n+1)%p-t.g-t.f)%p*i2%p; 
	return {F%p, G%p, H%p}; 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17