类欧几里得算法小记
类欧几里得算法大概是要求这样的一个东西：给定非负整数 \(a,b,c,n\)，求 \(f(a,b,c,n)=\sum\limits_{i=0}^{n}{\lfloor \frac{ai+b}{c}}\rfloor\)。
按道理来说整除问题一般是考虑除法分块，但是问题在于除法分块貌似适用范围是 \(i\) 在分母的情况。
我们不妨从简单的方面入手，讨论一些特殊情况：
Section 1 : \(a=0\)
显然 \(f(0,b,c,n)=\lfloor\frac{b}{c}\rfloor(n+1)\)
Section 2 : \(a\geq c\or b\geq c\)
这样的话我们希望缩减问题规模，使得 \(a,b\) 模上 \(c\)。
那么可以在下取整里面常数分离，得到
\[f(a,b,c,n)=\sum\limits_{i=1}^{n}{\lfloor\frac{a}{c}\rfloor i+\lfloor\frac{b}{c}\rfloor+\lfloor \frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor}\\
=\lfloor\frac{a}{c}\rfloor \frac{n(n+1)}{2}+\lfloor\frac{b}{c}\rfloor(n+1)+f(a\bmod c,b\bmod c,c,n)\\
\]
Section 3 : \(a<c\and b<c\)
令 \(m=\lfloor\frac{an+b}{c}\rfloor\)。考虑拆贡献，即拆成：
\[f(a,b,c,n)=\sum\limits_{i=0}^{n}{\sum\limits_{j=0}^{m-1}{[j<\lfloor \frac{ai+b}{c}\rfloor]}}
\]
先来化简一下中间那个式子：
\[j<\lfloor \frac{ai+b}{c}\rfloor \iff j+1\leq \frac{ai+b}{c}\iff ai> cj+c-b-1\iff i>\lfloor\frac{cj+c-b-1}{a}\rfloor
\]
那么原式就变成：
\[f(a,b,c,n)=\sum\limits_{j=0}^{m-1}n-\lfloor\frac{cj+c-b-1}{a}\rfloor=nm-f(c,c-b-1,a,m-1)
\]
可以发现上面三种情况包含了所有情况，也就是说如果我们这样递归已经可以计算答案了，但是这样的复杂度是多少呢？
分析复杂度的时候我们只关系 \(a,c\)，可以发现每两次操作第一次会取模，第二次会交换，这和 gcd 的过程几乎一样，因此复杂度 \(O(\log V)\)。这也是它和欧几里得算法唯一相似的地方。
例题 中还给了另外两个函数，也是类似的推法，所不同的是他们会互相转移，三个函数一起递推会方便一点。
submission