类欧几里得

题目

主要分析这道题目的做法，大致也就是类欧的用处。

设 \(f(a,b,c,n)=\sum_{i=0}^n \lfloor \frac{ai+b}{c} \rfloor,g(a,b,c,n)=\sum_{i=0}^n \lfloor \frac{ai+b}{c} \rfloor^2,h(a,b,c,n)=\sum_{i=0}^n i \lfloor \frac{ai+b}{c} \rfloor\)。

首先考虑 \(f\) 的转移：

设 \(m=\lfloor \frac{an+b}{c} \rfloor\) 。

• \(a=0: f(a,b,c,n)=(n+1) \lfloor \frac{b}{c} \rfloor\)。

• \(a \geq c\) 或 \(b \geq c:\)

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

\(=f(a \bmod c,b\bmod c,c,n)+\frac{n(n+1)}{2} \lfloor \frac{a}{c} \rfloor + (n+1) \lfloor \frac{b}{c} \rfloor\)

• \(else:\)

\(f(a,b,c,n)=\sum_{i=0}^n \sum_{j=1}^m [j \leq \lfloor \frac{ai+b}{c} \rfloor]\)

\(=\sum_{i=0}^n \sum_{j=0}^{m=1} [jc+c < ai+b+1]\)

\(=\sum_{j=0}^{m-1} \sum_{i=0}^n [jc+c < ai+b+1]\)

\(=\sum_{j=0}^{m-1} \sum_{i=0}^n [ai > jc+c-b-1]\)

\(=\sum_{j=0}^{m-1}(n-\lfloor \frac{jc+c-b-1}{a} \rfloor)\)

\(=nm-\sum_{j=0}^{m-1}(\lfloor \frac{jc+c-b-1}{a} \rfloor)\)

\(=nm-f(c,c-b-1,a,m-1)\)

然后就类似于一个递归的过程。

时间复杂度分析参考求 \(\gcd\) 的过程 ， \(\gcd(a,b)=\gcd(b,a \bmod b)\)，这个的时间复杂度是 \(\log n\) 的。

然后观察上面转移的 \(a,c\) 两维，容易得到相同的结论，所以时间复杂度也是 \(\log n\) 的。

然后考虑 \(g,h\) 的转移，这两个的转移相互之间需要互相递归，就一起写了。

• \(a=0:\)

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

\(h(a,b,c,n) = \frac{n(n+1)}{2} \lfloor \frac{b}{c} \rfloor\)

• \(a \geq c\) 或 \(b \geq c:\)

\(g(a,b,c,n)=\sum_{i=0}^n (\lfloor \frac{(a \bmod c)i+b \bmod c}{c} \rfloor+i \lfloor \frac{a}{c} \rfloor+\lfloor \frac{b}{c} \rfloor)^2\)

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

\(=g(a \bmod c,b \bmod c,c,n)+2 \lfloor \frac{a}{c} \rfloor h(a \bmod c,b \bmod c,c,n)+2 \lfloor \frac{b}{c} \rfloor f(a \bmod c,b \bmod c,c,n) + \frac{n(n+1)(2n+1)}{6} \lfloor \frac{a}{c} \rfloor^2+\frac{n(n+1)}{2} \lfloor \frac{a}{c} \rfloor \times \lfloor \frac{b}{c} \rfloor+(n+1) \lfloor \frac{b}{c} \rfloor^2\)

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

\(=h(a \bmod c,b \bmod c,c,n)+\frac{n(n+1)(2n+1)}{6} \lfloor \frac{a}{c} \rfloor + \frac{n(n+1)}{2} \lfloor \frac{b}{c} \rfloor\)

• \(else:\)

\(g(a,b,c,n)=2 \sum_{i=0}^n \sum_{j=1}^m[jc \leq ai+b]-f(a,b,c,n)\)

\(=2 \sum_{i=0}^n \sum_{j=0}^{m-1} j[jc + c < ai+b+1] + f(a,b,c,n)\)

\(=2 \sum_{j=0}^{m-1} j \sum_{i=0}^n [jc+c < a_i+b+1] + f(a,b,c,n)\)

\(=2 \sum_{j=0}^{m-1} j \sum_{i=0}^n [a_i > jc+c-b-1] + f(a,b,c,n)\)

\(=2 \sum_{j=0}^{m-1} j \sum_{i=0}^n (n-\lfloor \frac{jc+c-b-1}{a} \rfloor) + f(a,b,c,n)\)

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

\(h(a,b,c,n)=\sum_{i=0}^n i \sum_{j=1}^m [jc \leq ai+b]\)

\(=\sum_{i=0}^n i \sum_{j=0}^{m-1} [jc+c < ai+b+1]\)

\(=\sum_{j=0}^{m-1} \sum_{i=0}^n i[jc+c<ai+b+1]\)

\(=\frac{n(n+1)m}{2}-\frac{1}{2} (\sum_{j=0}^{m-1} \lfloor \frac{jc+c-b-1}{a} \rfloor ^2+\sum_{j=0}^{m-1} \lfloor \frac{jc+c-b-1}{a} \rfloor)\)

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

上面直接做时间复杂度就是 \(\Theta(T \log n)\)。

一个需要注意的小细节就是如果将三个分开来求会有很多算重的部分，时间复杂度比较大。

解决的方案是考虑将 \(f,g,h\) 定义在结构体当中转移，具体可以参考代码实现。

时间复杂度 \(\Theta(T \log n)\)。

代码