万能欧几里得

万欧得推式子.

万能欧几里得的作用是求一些类似辗转相除的算法,需要递归求解的东西.万能欧几里得的泛用性在于主板子基本不用换,只需要稍微修改合并部分的代码.

可以使用矩阵的思想.

1. 求

   $$\sum_{i=0}^{n}\left\lfloor\frac{ai+b}{c}\right\rfloor, \sum_{i=0}^{n}\left\lfloor\frac{ai+b}{c}\right\rfloor^{2}, \sum_{i=0}^{n}i\left\lfloor\frac{ai+b}{c}\right\rfloor$$

   设

   $$f(x)=\lfloor\frac{Px+R}Q\rfloor$$

   求：

   $$\sum_{i=1}^nf(i),\sum_{i=1}^nf^2(i),\sum_{i=1}^nif(i)$$

   下文设$y=f(x)$,即求：

   $$A=\sum y,B=\sum y^{2},C=\sum xy$$

   一般万欧都需要维护$U$和$R$的数量(记为$u$和$r$).

   合并两段信息 $I_0$与 $I_{1}$ ,结果为$I$ ,考虑增量:

   $$y\leftarrow y_1+u_0 \\ x\leftarrow x_1+r_0$$ $$\begin{aligned} A-A_0&=\sum y \\ &=\sum(y_1+u_0) \\ &=\sum y_1+u_0r_1 \\ &=A_1+u_0r_1 \\ B-B_{0} &=\sum y^2 \\ &=\sum(y_1+u_0)^2 \\ &=\sum y_1^2+2u_0\sum y_1+u_0^2r_1 \\ &=B_1+2u_0A_1+u_0^2r_1 \\ C-C_0 &=\sum xy \\ &=\sum(x_1+r_0)(y_1+u_0) \\ &=\sum x_1y_1+u_0\sum x_1+r_0\sum y_1+u_0r_0r_1 \\ &=C_1+u_0\frac{r_1(r_1+1)}2+r_0A_1+u_0r_0r_1 \end{aligned}$$

   也就是 $\sum$ 里面(y)加 $u$ ,外面加 $r$ .

   第二种证明方法:设

   $$\begin{aligned}f(a,b,c,n)=&\sum_{i=0}^n\Big\lfloor\frac{ai+b}{c}\Big\rfloor\\=&\sum_{i=0}^n\Big\lfloor\frac{(\lfloor\frac ac\rfloor c+a\mod c)i+(\lfloor\frac bc\rfloor c+b\mod c)}{c}\Big\rfloor\\=&\frac{n(n+1)}2\Big\lfloor\frac ac\Big\rfloor+(n+1)\Big\lfloor\frac bc\Big\rfloor+\sum_{i=0}^n\Big\lfloor\frac{(a\mod c)i+(b\mod c)}c\Big\rfloor \\=&\frac{n(n+1)}2\Big\lfloor\frac ac\Big\rfloor+(n+1)\Big\lfloor\frac bc\Big\rfloor+f(a\mod c,b\mod c,c,n)\end{aligned}$$

   改变一下求和项目看到

   $$\begin{aligned}f(a,b,c,n)&=\sum_{k=0}^{m-1}\sum_{i=0}^n\Big[i>\Big\lfloor\frac{jc+c-b-1}{a}\Big\rfloor\Big] \\&=\sum_{j=0}^{m-1}\Big(n-\Big\lfloor\frac{jc+c-b-a}a\Big\rfloor\Big) \\&=nm-f(c,c-b-1,a,m-1)\end{aligned}$$

   中间有

   $$n^2=2\frac{n(n+1)}2-n=\Big(\sum_{i=0}^ni\Big)-n$$

弊端

$$\sum\sqrt{y},\sum x^y,\sum a^{xy},\sum2^{2^y},\sum Asin(wy+\phi)$$

由于单维影响无法差分线性,即我们无法设计出一个好的矩阵来表达其值,所以上述式子均无法计算.