·前置芝士

·欧几里得算法

又称辗转相除法，举例如gcd求法，基本递归函数为\(f(a,b)=f(b,a\mod b)\)；

证明：a可以表示成\(a = kb + r\)（a,b,k,r皆为正整数，且\(r<b\)），则\(r = a \mod b\)。假设d是a,b的一个公约数，记作\(d|a\),\(d|b\)，即a和b都可以被d整除。而r = \(a - kb\)，两边同时除以d，\(r/d=a/d-kb/d=m\)，由等式右边可知m为整数，因此\(d|r\)因此d也是\(b,a \mod b\)的公约数。因\((a,b)\)和\((b,a\mod b)\)的公约数相等，则其最大公约数也相等。

·正文

·定义：定义函数\(f(a,b,c,n)=\sum_{i=0}^{n} \lfloor \frac{ai+b}{c} \rfloor\),其中a,b,c,d都是常数，我们要求算法复杂度为\(O(n \log n)\)

·求解方式：我们可以对该式子做一些处理：

​ ·对于\(a\geq c\)或\(b \geq c\)，我们可以直接将\(a\)和\(b\)对\(c\)取模以简化问题。将式子改变一下可得：

\(f(a,b,c,n)\)

\(=\sum_{i=0}^{n} \lfloor \frac{ai+b}{c} \rfloor\)

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

\(=\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}\)

\(=\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)\)

那么问题转化为了\(a<c\)且\(b<c\)的情况。接下来我们从该i下手，我们尝试合并贡献来计算。但是这个式子的贡献似乎不好合并。那么我们转化一下，将和的式子变成另一个格式：\(\sum_{i=0}^{n} \sum_{j=0}^{\lfloor \frac{ai+b}{c} \rfloor-1}1\)

然后我们来试试看搞一个和\(j\)有关的贡献式。我们可以用上面和式中的\(n\)限制\(i\)的上界，然后用\(i\)来限制\(j\)的上界。然后我们交换一下\(i\)，\(j\)的求和算子。得到：\(\sum_{j=0}^{\lfloor \frac{an+b}{c} \rfloor-1}\sum_{i=0}^{n}[j<\lfloor\frac{ai+b}{c}\rfloor]\)

然后我们来把下取整符号拿下，可得：\(j+1\leq\frac{ai+b}{c}\)

然后变换一下又有：\(jc+c-b-1<ai\)

然后我们向下取整：\(\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)\)

·代码：

long long f(long long a,long long b,long long c,long long n){
	if(a==0)return((b/c)*(n+1));
	if(a>=c||b>=c)return f(a%c,b%c,c,n)+(a/c)*n*(n+1)/2+(b/c)*(n+1);
	long long m=(a*n+b)/c;
	return n*m-f(c,c-b-1,a,m-1);
}

·扩展：

给出另外两个定义：

定义\(g(a,b,c,n)=\sum_{i=0}^{n}i\lfloor\frac{ai+b}{c}\rfloor\)，\(h(a,b,c,n)=\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor^2\)

·关于g的解法：

首先取模，有：\(g(a,b,c,n)=g(a\mod c,b\mod c,c,n)+\lfloor\frac{a}{c}\rfloor \frac{n(n+1)(2n+1)}{6}+\lfloor\frac{b}{c}\rfloor\frac{n(n+1)}{2}\)

然后考虑\(a<c\)且\(b<c\)，依旧令\(m=\lfloor\frac{an+b}{c}\rfloor\)，有：

\(g(a,b,c,n)=\frac{1}{2}[mn(n+1)-h(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)]\)

·关于h的解法：

首先取模，有\(h(a,b,c,n)=h(a\mod c,b\mod c,c,n)+2\lfloor\frac{b}{c}\rfloor f(a\mod c,b\mod c,c,n)+\)

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

然后考虑\(a<c\)且\(b<c\)，令\(m=\lfloor\frac{an+b}{c}\rfloor\)，有：

\(h(a,b,c,n)=nm(m+1)-2g(c,c-b-1,a,m-1)-2f(c,c-b-1,a,m-1)-f(a,b,c,n)\)

对于以上几种定义可以同步进行计算。

（PS:关于这一部分的具体推导过程请看参考资料部分）

·参考资料：

https://oi-wiki.org/math/euclidean/