首页 > 笔记 > 类欧几里得算法总结

类欧几里得算法总结

雅礼集训某天的东西。。

定义

首先写下定义,其实就是几个式子。

$$f(a,b,c,n)=\sum_{i=0}^n\lfloor {ai+b \over c} \rfloor$$

$$g(a,b,c,n)=\sum_{i=0}^ni\lfloor {ai+b \over c} \rfloor$$

$$h(a,b,c,n)=\sum_{i=0}^n\lfloor {ai+b \over c} \rfloor^2$$

类欧几里得就是如何快速求这几个式子。下面先推第一个,第二个要用到第一个,第三个要用到第二个。

为了方便(懒),下面下取整都不写了,而且$m={an+b \over c}$

f

当$c \leq a$或者$c \leq b$的时候,这样就可以把后面的式子拆开,整除的算一部分,余数算一部分。也就是

$$f(a,b,c,n)={a\over c}\times n \times {n+1 \over 2} +{b \over c} \times (n+1)+f(a \%c,b\%c,c,n)$$

那$a$和$b$都小于$c$怎么办呢?

我们可以从几何的角度来理解这个式子,可以发现$\sum$里面的式子很像一个直线的解析式。意义其实是一条倾斜直线与$x=0$和$x=n$两条铅垂线组成的直角梯形内整点数量(不包括纵坐标为0的点,包括在线上的点)。

这个式子就是在枚举一条纵线,统计上面的整点。现在我们可以枚举一个横线,再统计上面的点的个数。

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

这样的话看上去效率好像更低了。但是这个式子能化啊= =

先把$c$乘过去,再把$b$移过去

$$=\sum_{i=0}^n\sum_{j=0}^{m-1}[ai \geq cj+c-b]$$

减上$1$把大于等于化成等于,把$a$除过去

$$=\sum_{i=0}^n\sum_{j=0}^{m-1}[i>{cj+c-b-1 \over a}]$$

这样就可以不枚举第一层了,直接化成$n$。(次数是一样的)

$$=\sum_{j=0}^{m}(n-{cj+c-b-1 \over a})$$

把这个$\sum$拆开

$$=m\times n-\sum_{j=0}^{m}{cj+c-b-1 \over a}$$

这样就能看出来了吧,这就是$f$!

$$f(a,b,c,n)=m\times n-f(c,c-b-1,a,m-1)$$

发现又可以递归了,其实把$m$带入一下:

$$f(a,b,c,n)={an+b \over c}\times n-f(c,c-b-1,a,{an+b \over c}-1)$$

这样每次由$(a,c)$变成$(c,a\%c)$,因此复杂度与欧几里得算法一致,也就是$O(\log n)$

g

当$c \leq a$或者$c \leq b$的时候,和上面一样,就是需要用一下平方和公式。

$$g(a,b,c,n)={a\over c}\times n \times (n+1)\times {2n+1 \over 6}+{b\over c}\times n\times {n+1\over 2}+g(a\%c,b\%c,c,n)$$

$a$和$b$都小于$c$和上面一样推

$$g(a,b,c,n)=\sum_{i=0}^ni\sum_{j=0}^{m-1}[{ai+b \over c} \geq j+1]$$

$$=\sum_{i=0}^ni\sum_{j=0}^{m-1}[i>{cj+c-b-1 \over a}]$$

这里因为多了一位,所以要套一下求和公式

$$={1\over2}\sum_{j=0}^{m-1}(n+1+{cj+c-b-1 \over a})\times(n-{cj+c-b-1 \over a})$$

把它乘开

$$={1\over2}\sum_{j=0}^{m-1}n\times (n+1)-{cj+c-b-1 \over a}+({cj+c-b-1 \over a})^2$$

发现前面的是$f$,后面的是$g$

$$g(a,b,c,n)={1 \over 2}[(n+1)\times n\times m-f(c,c-b-1,a,m-1)-g(c,c-b-1,a,m-1) ]$$

h

当$c \leq a$或者$c \leq b$的时候,也很麻烦。。

$$h(a,b,c,n)=({a\over c})^2\times {n(n+1)(2n+1)\over 6}+({b\over c})^2\times(n+1)+{a\over c}\times{b\over c}\times n(n+1)+h(a\%c,b\%c,c,n)+2\times {a\over c}\times g(a\%c,b\%c,c,n)+2\times {b\over c}\times f(a\%c,b\%c,c,n)$$

推剩下的情况就和上面的不一样了。

我们先试着构造一个$n^2$

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

那么我们就把$({ai+b\over c})^2$拆开

$$h(a,b,c,n)=\sum_{i=0}^n(2\times \sum_{j=1}^{(ai+b)/c}j-{ai+b\over c})$$

这样拆出一个$f$,再交换一下主体

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

和前面一样的化

$$h(a,b,c,n)=2\times \sum_{j=0}^{m-1}(j+1)*(n-{cj+c-b-1 \over a})-f(a,b,c,n)$$

那最后就成了

$$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)$$

例题 bzoj 3817

题意

给定$n\leq 10^9,r\leq10^4$求

$$\large \sum_{d=1}^{n} (-1)^{\lfloor \sqrt{d\times r\times d} \rfloor}$$

题解

设$x=\sqrt r$,则

$$
\begin{align}
-1^{dx } & =1-2( dx \% 2) \\
&=1-2(dx - \frac{dx}{2} * 2) \\
&= 1+4\frac{dx}{2} + 2 dx
\end{align}
$$

那么

$$原式 =n + 4 \sum_{d=1}^{n} \frac{dx}{2}-2\sum_{d=1}^{n}dx$$

这样就是类欧的式子了。

代码


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×