类欧几里得算法

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132718582

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

推式子步骤：

分类讨论

$a=0$

是个最简式子

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

由 $f(a\bmod c,b\bmod 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); 
}

对于 $\sum\limits_{i=0}^{n}{\lfloor \frac{ai+b}{c} \rfloor}^2\,,\ \sum\limits_{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}; 
}