类欧几里得算法入门

类欧几里得是统计直线下整点贡献的一种套路，最常见的类欧几里得是求：

$$\sum^{n}_{i=0} \left \lfloor \frac{ai+b}{c} \right \rfloor$$

也就是直线$\frac{ax+b}{c}$下纵坐标大于$0$的整点数。
要求$a,b\ge 0,c>0$。

第一次推类欧几里得，还是写的详细一点。

首先我们要知道几个关系：
$$\left \lfloor \frac{a}{b} \right \rfloor \ge c \Leftrightarrow a \ge bc$$
$$\left \lceil \frac{a}{b} \right \rceil \le c \Leftrightarrow a \le bc$$
$$\left \lfloor \frac{a}{b} \right \rfloor < c \Leftrightarrow a < bc$$
$$\left \lceil \frac{a}{b} \right \rceil > c \Leftrightarrow a > bc$$

这个其实很好记，如果有等号的话就说明可以挨到，那就让他尽量接近，所以取整取离$c$近的那一边。
反之，如果没有等号说明挨不到，那么就要让它尽量避免“接触”$c$，所以取整取离$c$远的那一边。

如果满足大小关系但是取整符号相反可以使用下面式子转化：

$$\left \lceil \frac{a}{b} \right \rceil = \left \lfloor \frac{a + b - 1}{b} \right \rfloor$$
$$\left \lfloor \frac{a}{b} \right \rfloor = \left \lceil \frac{a - b + 1}{b} \right \rceil$$

这个也很好记，因为"$-1/+1$"相当于把取整符号"移到下面/上面"，但是因为取整本身差"$1$"，于是就要相应地$+b/-b$。

熟悉这些还是有很大好处的，理解了上面这些转化后我们开始推导类欧几里得。

首先考虑这样两个情况：
#### 情况1:
$$b\ge c\Leftrightarrow\sum^{n}_{i=0} \left \lfloor \frac{ai+b}{c} \right \rfloor=\sum^{n}_{i=0} \left \lfloor \frac{ai+b\%c}{c} \right \rfloor+\left\lfloor\frac{b}{c}\right\rfloor(n+1)$$
为什么正确呢，考虑我们把一条直线往下平移$\left\lfloor\frac{b}{c}\right\rfloor$个单位，并且平移后截距依然是正整数，那么在这个过程中每一个横坐标被移到界外的点都是$\left\lfloor\frac{b}{c}\right\rfloor$，就是$(n+1)\times \left\lfloor\frac{b}{c}\right\rfloor$ (*:有$i=0$的时候，故为$(n+1)$)个点。

#### 情况2:

$$a\ge c\Leftrightarrow\sum^{n}_{i=0} \left \lfloor \frac{ai+b}{c} \right \rfloor=\sum^{n}_{i=0} \left \lfloor \frac{(a\%c)i+b}{c} \right \rfloor+\left\lfloor\frac{a}{c}\right\rfloor\frac{n(n+1)}{2}$$
类似于上面的思考模式，只是$i$每$+1$移出边界的点数就$+1$。所以是一个等差数列求和。

问题转化为了令人惊喜的模式！
因为只要$a\le c\ or\ b \le c$，$a,b$就可以被转化为$\% c$的形式，只要我们解决$a,b<c$的情况就可以类似欧几里得算法一样递归下去了。

现在我们来看一下这个式子。

$$\sum^{n}_{i=0} \left \lfloor \frac{ai+b}{c} \right \rfloor$$

无法下手，考虑交换和号

$$=\sum^{n}_{i=0} \sum^{\lfloor \frac{ai+b}{c} \rfloor}_{j=1}1$$

$$=\sum^{n}_{i=0} \sum^{\lfloor \frac{an+b}{c} \rfloor}_{j=1}\left[\left \lfloor \frac{ai+b}{c} \right \rfloor\ge j\right]$$

$$=\sum^{\lfloor \frac{an+b}{c} \rfloor}_{j=1}\sum^{n}_{i=0} \left [\left \lfloor \frac{ai+b}{c} \right \rfloor\ge j\right]$$

使用结论

$$=\sum^{\lfloor \frac{an+b}{c} \rfloor}_{j=1}\sum^{n}_{i=0} \left [ai+b\ge cj\right]$$

$$=\sum^{\lfloor \frac{an+b}{c} \rfloor}_{j=1}\sum^{n}_{i=0} \left [i\ge \left\lceil \frac{cj-b}{a}\right\rceil \right]$$

$$=\sum^{\lfloor \frac{an+b}{c} \rfloor}_{j=1}\left (n - \left\lceil \frac{cj-b}{a}\right\rceil + 1\right)$$

$$=\sum^{\lfloor \frac{an+b}{c} \rfloor}_{j=1}\left (n - \left\lfloor \frac{cj+a-b-1}{a}\right\rfloor + 1\right)$$

$$=n\left\lfloor \frac{an+b}{c} \right\rfloor-\sum^{\lfloor \frac{an+b}{c} \rfloor}_{j=1}\left (\left\lfloor \frac{cj+a-b-1}{a}\right\rfloor - 1\right)$$

离成功只有一步之遥，我们只需要把$j$划归为$0$下标开始就递归成了新的问题。于是用$j+1$换$j$。

$$=n\left\lfloor \frac{an+b}{c} \right\rfloor-\sum^{\lfloor \frac{an+b}{c} \rfloor-1}_{j=0}\left (\left\lfloor \frac{c(j+1)+a-b-1}{a}\right\rfloor - 1\right)$$

$$=n\left\lfloor \frac{an+b}{c} \right\rfloor-\sum^{\lfloor \frac{an+b}{c} \rfloor-1}_{j=0}\left (\left\lfloor \frac{cj+c-b-1}{a}\right\rfloor\right)$$

发现右边递归成为了子问题，继续一轮操作就好了

Rockdu's Blog

导航

最近发表

大佬们的友链