「学习笔记」类欧几里得算法
Coffee_zzz
·
·
算法·理论
类欧几里得算法是用于在 \mathcal O(\log n) 的复杂度内求解下式的算法：
f(a,b,c,n)=\sum_{i=0}^n\left\lfloor\dfrac {ai+b} c\right\rfloor
首先考虑 a \ge c 或 b \ge c 的情况：
\begin{aligned}
f(a,b,c,n)&=\sum_{i=0}^n\left\lfloor\dfrac {ai+b} c\right\rfloor\\
&=\sum_{i=0}^n\left\lfloor\dfrac {\left(c\left\lfloor\frac a c\right\rfloor+(a \bmod c) \right)i+\left(c\left\lfloor\frac b c\right\rfloor+(b \bmod c)\right)} c\right\rfloor\\
&=\sum_{i=0}^n\left(\left\lfloor \frac a c\right\rfloor i+\left\lfloor \frac b c\right\rfloor\right)+\sum_{i=0}^n \left\lfloor\dfrac {(a \bmod c )i+(b \bmod c)} c\right\rfloor\\
&=\left\lfloor \frac a c\right\rfloor \dfrac {n(n+1)} 2 + \left\lfloor \frac b c\right\rfloor(n+1)+f(a \bmod c,b \bmod c,c,n)
\end{aligned}
接下来考虑 a \lt c 且 b \lt c 的情况：
\begin{aligned}
f(a,b,c,n)&=\sum_{i=0}^n\left\lfloor\dfrac {ai+b} c\right\rfloor\\
&=\sum_{i=0}^n \sum_{j=0}^{\left\lfloor\frac {ai+b} c\right\rfloor-1} 1
\end{aligned}
设 m=\left\lfloor\dfrac {an+b} c\right\rfloor，继续推式子：
\begin{aligned}
f(a,b,c,n)&=\sum_{i=0}^n \sum_{j=0}^{\left\lfloor\frac {ai+b} c\right\rfloor-1} 1\\
&= \sum_{j=0}^{m-1} \sum_{i=0}^n \left[j \lt \left\lfloor \dfrac {ai+b} c\right\rfloor \right]\\
&= \sum_{j=0}^{m-1} \sum_{i=0}^n \left[j+1 \le \left\lfloor \dfrac {ai+b} c\right\rfloor \right]\\
&= \sum_{j=0}^{m-1} \sum_{i=0}^n \left[j+1 \le \dfrac {ai+b} c \right]\\
&= \sum_{j=0}^{m-1} \sum_{i=0}^n \left[cj+c-b \le ai \right]\\
&= \sum_{j=0}^{m-1} \sum_{i=0}^n \left[cj+c-b-1 \lt ai \right]\\
&= \sum_{j=0}^{m-1} \sum_{i=0}^n \left[\dfrac {cj+c-b-1} a \lt i \right]\\
&= \sum_{j=0}^{m-1} \sum_{i=0}^n \left[\left\lfloor\dfrac {cj+c-b-1} a\right\rfloor \lt i \right]\\
&= \sum_{j=0}^{m-1} \left(n-\left\lfloor\dfrac {cj+c-b-1} a\right\rfloor\right)\\
&= nm-\sum_{j=0}^{m-1} \left\lfloor\dfrac {cj+c-b-1} a\right\rfloor\\
&= nm-f(c,c-b-1,a,m-1)
\end{aligned}
容易发现，在函数 f 中，a,c 是在不断交换和取模的，是辗转相除的过程，和欧几里得算法十分类似，时间复杂度即为 \mathcal O(\log n)。
类欧几里得算法也有许多拓展，例如下面的两个求和式：
g(a,b,c,n)=\sum_{i=0}^ni\left\lfloor\dfrac {ai+b} c\right\rfloor\\
h(a,b,c,n)=\sum_{i=0}^n\left\lfloor\dfrac {ai+b} c\right\rfloor^2
我们分别考虑如何求值。
对于函数 g，首先考虑 a \ge c 或 b \ge c 的情况：
\begin{aligned}
g(a,b,c,n)&=\sum_{i=0}^ni\left\lfloor\dfrac {ai+b} c\right\rfloor\\
&=\sum_{i=0}^ni\left\lfloor\dfrac {\left(c\left\lfloor\frac a c\right\rfloor+(a \bmod c) \right)i+\left(c\left\lfloor\frac b c\right\rfloor+(b \bmod c)\right)} c\right\rfloor\\
&=\sum_{i=0}^n\left(\left\lfloor \frac a c\right\rfloor i^2+\left\lfloor \frac b c\right\rfloor i \right)+\sum_{i=0}^n i\left\lfloor\dfrac {(a \bmod c )i+(b \bmod c)} c\right\rfloor\\
&=\left\lfloor \frac a c\right\rfloor \dfrac {n(n+1)(2n+1)} 6 + \left\lfloor \frac b c\right\rfloor \dfrac {n(n+1)} 2+g(a \bmod c,b \bmod c,c,n)
\end{aligned}
接下来考虑 a \lt c 且 b \lt c 的情况：
\begin{aligned}
f(a,b,c,n)&=\sum_{i=0}^n i\left\lfloor\dfrac {ai+b} c\right\rfloor\\
&=\sum_{i=0}^n \sum_{j=0}^{\left\lfloor\frac {ai+b} c\right\rfloor-1} i
\end{aligned}
设 m=\left\lfloor\dfrac {an+b} c\right\rfloor：
\begin{aligned}
g(a,b,c,n)&=\sum_{i=0}^n \sum_{j=0}^{\left\lfloor\frac {ai+b} c\right\rfloor-1} i\\
&= \sum_{j=0}^{m-1} \sum_{i=0}^n \left[j \lt \left\lfloor \dfrac {ai+b} c\right\rfloor \right] i\\
&= \sum_{j=0}^{m-1} \sum_{i=0}^n \left[\left\lfloor\dfrac {cj+c-b-1} a\right\rfloor \lt i \right] i\\
\end{aligned}
设 k=\left\lfloor\dfrac {cj+c-b-1} a\right\rfloor：
\begin{aligned}
g(a,b,c,n)&= \sum_{j=0}^{m-1} \sum_{i=0}^n \left[\left\lfloor\dfrac {cj+c-b-1} a\right\rfloor \lt i \right] i\\
&= \sum_{j=0}^{m-1} \sum_{i=0}^n \left[k \lt i \right] i\\
&= \sum_{j=0}^{m-1} \sum_{i=k+1}^n i\\
&= \sum_{j=0}^{m-1} \dfrac {(n+k+1)(n-k)} 2\\
&= \sum_{j=0}^{m-1} \dfrac {n^2+n-k-k^2} 2\\
&= \dfrac 1 2 \left( mn^2+mn-\sum_{j=0}^{m-1} k - \sum_{j=0}^{m-1} k^2\right)\\
&= \dfrac 1 2 \left( mn^2+mn-f(c,c-b-1,a,m-1) - h(c,c-b-1,a,m-1)\right)\\
\end{aligned}
对于函数 h，我们首先考虑下面的等式：
n^2=\left(\sum_{i=1}^n i\right)-n
我们可以利用这个等式，避免出现两个求和式的乘积。
接下来考虑 a \ge c 或 b \ge c 的情况：
\begin{aligned}
h(a,b,c,n)&=\sum_{i=0}^n\left\lfloor\dfrac {ai+b} c\right\rfloor^2\\
&=\sum_{i=0}^n\left\lfloor\dfrac {\left(c\left\lfloor\frac a c\right\rfloor+(a \bmod c) \right)i+\left(c\left\lfloor\frac b c\right\rfloor+(b \bmod c)\right)} c\right\rfloor^2\\
&=\sum_{i=0}^n \left(\left\lfloor\dfrac {(a \bmod c)i+(b \bmod c)} c\right\rfloor+\left\lfloor\dfrac a c\right\rfloor i + \left\lfloor\dfrac b c\right\rfloor\right)^2\\
&=\sum_{i=0}^n \left\lfloor\dfrac {(a \bmod c)i+(b \bmod c)} c\right\rfloor^2+\sum_{i=0}^n 2\left(\left\lfloor\dfrac a c\right\rfloor i + \left\lfloor\dfrac b c\right\rfloor\right)\left\lfloor\dfrac {(a \bmod c)i+(b \bmod c)} c\right\rfloor+\sum_{i=0}^n\left(\left\lfloor\dfrac a c\right\rfloor i + \left\lfloor\dfrac b c\right\rfloor\right)^2\\
&=\sum_{i=0}^n \left\lfloor\dfrac {(a \bmod c)i+(b \bmod c)} c\right\rfloor^2+2\left\lfloor\dfrac a c\right\rfloor \sum_{i=0}^n i \left\lfloor\dfrac {(a \bmod c)i+(b \bmod c)} c\right\rfloor+ 2 \left\lfloor\dfrac b c\right\rfloor\sum_{i=0}^n \left\lfloor\dfrac {(a \bmod c)i+(b \bmod c)} c\right\rfloor+
\sum_{i=0}^n\left\lfloor\dfrac a c\right\rfloor^2 i^2 + \sum_{i=0}^n2\left\lfloor\dfrac a c\right\rfloor\left\lfloor\dfrac b c\right\rfloor i+\sum_{i=0}^n\left\lfloor\dfrac b c\right\rfloor^2\\
&=h(a \bmod c,b\bmod c,c,n)+
2\left\lfloor\dfrac a c\right\rfloor g(a\bmod c,b\bmod c,c,n)+ 2 \left\lfloor\dfrac b c\right\rfloor f(a\bmod c,b\bmod c,c,n)+
\left\lfloor\dfrac a c\right\rfloor^2 \dfrac {n(n+1)(2n+1)}{6} + \left\lfloor\dfrac a c\right\rfloor\left\lfloor\dfrac b c\right\rfloor n(n+1)+(n+1)\left\lfloor\dfrac b c\right\rfloor^2\\
\end{aligned}
最后考虑 a \lt c 且 b \lt c 的情况：
\begin{aligned}
h(a,b,c,n)&=\sum_{i=0}^n\left\lfloor\dfrac {ai+b} c\right\rfloor^2\\
&=\sum_{i=0}^n \left(\left(2\sum_{j=1}^{\left\lfloor\frac {ai+b} c\right\rfloor} j\right)-\left\lfloor\dfrac {ai+b} c\right\rfloor\right)\\
&= \left(2\sum_{i=0}^n\sum_{j=1}^{\left\lfloor\frac {ai+b} c\right\rfloor} j\right)-\sum_{i=0}^n \left\lfloor\dfrac {ai+b} c\right\rfloor\\
&= \left(2\sum_{i=0}^n\sum_{j=0}^{\left\lfloor\frac {ai+b} c\right\rfloor-1} (j+1)\right)-f(a,b,c,n)
\end{aligned}
设 m=\left\lfloor\dfrac {an+b} c\right\rfloor：
\begin{aligned}
h(a,b,c,n)&= \left(2\sum_{i=0}^n\sum_{j=0}^{\left\lfloor\frac {ai+b} c\right\rfloor-1} (j+1)\right)-f(a,b,c,n)\\
&=\left(2\sum_{j=0}^{m-1}\sum_{i=0}^n \left[j \lt \left\lfloor \dfrac {ai+b} c\right\rfloor \right](j+1)\right)-f(a,b,c,n)\\
&=\left(2\sum_{j=0}^{m-1}\sum_{i=0}^n \left[\left\lfloor\dfrac {cj+c-b-1} a\right\rfloor \lt i \right](j+1)\right)-f(a,b,c,n)\\
\end{aligned}
设 k=\left\lfloor\dfrac {cj+c-b-1} a\right\rfloor：
\begin{aligned}
h(a,b,c,n)&=\left(2\sum_{j=0}^{m-1}\sum_{i=0}^n \left[\left\lfloor\dfrac {cj+c-b-1} a\right\rfloor \lt i \right](j+1)\right)-f(a,b,c,n)\\
&=\left(2\sum_{j=0}^{m-1}\sum_{i=0}^n \left[k \lt i \right](j+1)\right)-f(a,b,c,n)\\
&=\left(2\sum_{j=0}^{m-1}(n-k)(j+1)\right)-f(a,b,c,n)\\
&=nm(m+1)-2\sum_{j=0}^{m-1} k-2\sum_{j=0}^{m-1} jk-f(a,b,c,n)\\
&=nm(m+1)-2f(c,c-b-1,a,m-1)-2g(c,c-b-1,a,m-1)-f(a,b,c,n)
\end{aligned}
同时计算 f,g,h 即可，时间复杂度同样为 \mathcal O(\log n)。