浅谈类欧几里得算法

类欧入门手册。 ### Background 类欧几里得算法主要解决直线下整点个数问题，像这样： > 给定一个函数 $f(x)=\frac{ax+b}{c}$，求当 $x\in [0,n]$ 且 $x \in \mathbf Z$ 时，$f(x)$ 下的整点个数之和是多少。 不难发现可以转化为一个求和的式子： $$\sum\limits_{i=0}^n \left\lfloor\frac{ai+b}{c}\right\rfloor$$ 我们今天就来解决这个问题。 ### Lemma 1 注：这一部分里的转换名称是我自己起的。 **求和转换** 为将一个数转换为若干个 $1$ 加起来的形式，如下所述： $$p=\sum\limits_{i=1}^p 1$$ ### Lemma 2 注：这一部分里的转换名称不是我自己起的。 **限制转换** 为当有两个求和第二个求和被第一个求和约束时，交换两个约束取消第二个求和被第一个求和的约束条件时，需要加上一个条件不等式作为第二个求和的约束，如下所述： $$\sum\limits_{i=1}^n \sum\limits_{j=1}^i p(i,j)=\sum\limits_{j=1}^n \sum\limits_{i=1}^n p(i,j)[j \le i]$$ ### Sample 1 >给定 $n,a,b,c$，求： > >$$\sum\limits_{i=0}^n \left\lfloor\frac{ai+b}{c}\right\rfloor$$ （试题链接 $\to $ [Link](https://www.luogu.com.cn/problem/P5170) 的第一部分） Lamma 1 & 2 看起来比较基础，但在类欧式子的推导中有很重要的作用。 我们将 **求和转换** 和 **限制转换** 一口气使用在这个式子上： $$\begin{aligned}\sum\limits_{i=0}^n \left\lfloor\frac{ai+b}{c}\right\rfloor&=\sum\limits_{i=0}^n \sum\limits_{j=0}^{\left\lfloor\frac{ai+b}{c}\right\rfloor-1}1\\&=\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\sum\limits_{i=0}^n 1\left[j<\left\lfloor\frac{ai+b}{c}\right\rfloor\right]\end{aligned}$$ 然后我们化简一下条件式里的不等式： $$\begin{aligned}j<\left\lfloor\frac{ai+b}{c}\right\rfloor&\to j+1 \le \left\lfloor\frac{ai+b}{c}\right\rfloor\\&\to j+1 \le \frac{ai+b}{c}\\&\to jc+c \le ai+b\\&\to jc+c-b-1 <ai\\&\to i>\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\end{aligned}$$ 我们将其化简为 $i>p$ 的形式是便于将其进行像下面这样的化简： $$\sum\limits_{i=0}^n 1[i>p]=\sum\limits_{i=p+1}^n 1$$ 所以将上面那个式子代入： $$\begin{aligned}\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\sum\limits_{i=0}^n 1\left[j<\left\lfloor\frac{ai+b}{c}\right\rfloor\right]&=\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\sum\limits_{i=0}^n 1\left[i>\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\right]\\&=\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\sum\limits_{i=\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor+1}^n1\end{aligned}$$ 然后我们把 **求和转换** 反过来用代入：即： $$\begin{aligned}\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\sum\limits_{i=\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor+1}^n1&=\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}n-\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\\&=\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}n-\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\\&=n\left\lfloor\frac{an+b}{c}\right\rfloor-\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\end{aligned}$$ 好，我们化简完了，因为这个式子可以递归，后面这个式子跟我们要化简的式子模式是一样的，并且这个是优于暴力的，复杂度大概 $\mathcal O(\log n)$。 ### Summary 1 经过上面的推导，不难发现，类欧算法即为下面四个部分： - 求和转化 - 限制转化 - 将限制转化得到的不等式转化为 $i$ 与某个式子的大小关系 - 代入后进一步推导成递归的模式 是不是没有想象中的那么难？ ### Practice 1 - [[BJOI 2012] 算不出的等式](https://www.luogu.com.cn/problem/P4132) 板题 - [loj 6245 红太阳](https://loj.ac/problem/6245) 将题目化为： $$\sum\limits_{i=0}^n\left\lfloor\frac{ai}{c}\right\rfloor$$ 后也是个板题。 ### Lemma 3 $$n^2=2\sum\limits_{i=1}^ni-n$$ 简证： $$\begin{aligned}2\sum\limits_{i=1}^ni-n&=2\dfrac{n(n+1)}{2}-n\\&=n(n+1)-n\\&=n^2\end{aligned}$$ ### Sample 2 > 给定 $n,a,b,c$，求： > > $$\sum\limits_{i=0}^n i\left\lfloor\frac{ai+b}{c}\right\rfloor$$ > $$\sum\limits_{i=0}^n \left\lfloor\frac{ai+b}{c}\right\rfloor^2$$ （试题链接 $\to$ [Link](https://www.luogu.com.cn/problem/P5170) 的二、三部分） 那么我们按照 Summary 1 总结的步骤开始吧！ $$\begin{aligned}\sum\limits_{i=0}^n i\left\lfloor\frac{ai+b}{c}\right\rfloor&=\sum\limits_{i=0}^n \sum\limits_{j=0}^{\left\lfloor\frac{ai+b}{c}\right\rfloor-1}i\\&=\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\sum\limits_{i=0}^ni\left[j<\left\lfloor\frac{ai+b}{c}\right\rfloor\right]\end{aligned}$$ 化简不等式： $$\begin{aligned}j<\left\lfloor\frac{ai+b}{c}\right\rfloor&\to j+1 \le \frac{ai+b}{c}\\&\to jc+c \le ai+b\\&\to jc+c-b-1<ai\\&\to i>\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\end{aligned}$$ 代入： $$\begin{aligned}\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\sum\limits_{i=0}^ni\left[j<\left\lfloor\frac{ai+b}{c}\right\rfloor\right]&=\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\sum\limits_{i=0}^ni\left[i>\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\right]\\&=\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\sum\limits_{i=\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor+1}^n i\\&= \sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left(\sum\limits_{i=1}^ni-\sum\limits_{i=1}^{\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor}i\right)\end{aligned}$$ 代入等差数列求和公式： $$\begin{aligned}\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left(\sum\limits_{i=1}^ni-\sum\limits_{i=1}^{\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor}i\right)&=\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left(\dfrac{n(n+1)}{2}-\dfrac{\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\left(\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\right)}{2}\right)\\&=\dfrac{1}{2}\left(\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}n(n+1)-\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor^2-\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\right)\\&=\dfrac{1}{2}\left(\left\lfloor\frac{an+b}{c}\right\rfloor n(n+1)-\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor^2-\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\right)\end{aligned}$$ 不难发现，最后一个式子里两个求和式子分别为 Sample 2 的第二个式子和 Sample 1 的式子。 接下来化简第二个式子，代入 Lemma 3： $$\begin{aligned}\sum\limits_{i=0}^n \left\lfloor\frac{ai+b}{c}\right\rfloor^2&=\sum\limits_{i=0}^n\left(2\sum\limits_{j=1}^{\left\lfloor\frac{ai+b}{c}\right\rfloor}j-\left\lfloor\frac{ai+b}{c}\right\rfloor\right)\\&=2\sum\limits_{i=0}^n\sum\limits_{j=1}^{\left\lfloor\frac{ai+b}{c}\right\rfloor}j-\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\end{aligned}$$ 减号后面的就是 Sample 1，我们接着化简减号前面的，并且再次代入两个转换： $$\begin{aligned}2\sum\limits_{i=0}^n\sum\limits_{j=1}^{\left\lfloor\frac{ai+b}{c}\right\rfloor}j&=2\sum\limits_{i=0}^n \sum\limits_{j=0}^{\left\lfloor\frac{ai+b}{c}\right\rfloor-1}(j+1)\\&=2\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\sum\limits_{i=0}^n(j+1)\left[j<\left\lfloor\frac{ai+b}{c}\right\rfloor\right]\end{aligned}$$ 化简不等式： $$\begin{aligned}j<\left\lfloor\frac{ai+b}{c}\right\rfloor&\to j+1 \le \frac{ai+b}{c}\\&\to jc+c \le ai+b\\&\to jc+c-b-1<ai\\&\to i>\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\end{aligned}$$ 代入： $$\begin{aligned}2\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\sum\limits_{i=0}^n(j+1)\left[j<\left\lfloor\frac{ai+b}{c}\right\rfloor\right]&=2\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\sum\limits_{i=0}^n(j+1)\left[i>\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\right]\\&=2\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\sum\limits_{i=\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor+1}^n(j+1)\\&=2\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}(j+1)\left(n-\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\right)\\&=2\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}n(j+1)-2\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor(j+1)\\&=n\left\lfloor\frac{an+b}{c}\right\rfloor\left(\left\lfloor\frac{an+b}{c}\right\rfloor+1\right)-2\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}j\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor j-2\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\end{aligned}$$ 这个部分包括了 Sample 2 的第一个式子和 Sample 1，当我们要求 Sample 2 的这两个式子的时候，可以考虑和 Sample 1 一块递归，总体时间复杂度依然是 $\mathcal O(\log n)$ 的。 ### Summary 2 第一个式子仍然跟 Sample 1 差不多，只不过最后一步用上了等差数列求和。 第二个式子需要先用 Lemma 3 进行一步化简再进行 Sample 1 的步骤。 ### Practice 2 - dWoi R2 D，等比赛结束后将会公布这题。 ### Summary End 本文只是类欧几里得算法的简介，或者入门手册，只讲解类欧几里得算法最基础的思路： - 两个转换 - 不等式化简 - 代入递推 经过不同的组合就会产生不同的题目。 ### Practice End 比较综合的两道题目，笔者并不是很会这两道题的所有步骤，因此只会把关键步骤写出来。 - [Codeforces 1182F Maxinum Sine](https://www.luogu.com.cn/problem/CF1182F) 将题目要求的东西转化为 $|2px \bmod 2q-q|$ 的最小值之后，进行二分，二分的 check 需要类欧，最后要用 exgcd 解，比较综合的题。 - [Codeforces 1098E Fedya the Potter](https://www.luogu.com.cn/problem/CF1098E) 运用双指针框定区间，然后二分，仍然是 check 函数里需要运用类欧。 ### Reference 1. [OI-Wiki 类欧几里得算法](https://oi-wiki.org/math/euclidean/)。 2. [AThousandMoon CF1182F 的题解](https://www.luogu.com.cn/blog/WDLGZH2017/solution-cf1182f)。