类欧入门手册。
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 的第一部分）
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] 算不出的等式 板题
- loj 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 的二、三部分）
那么我们按照 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
Summary End
本文只是类欧几里得算法的简介，或者入门手册，只讲解类欧几里得算法最基础的思路：
经过不同的组合就会产生不同的题目。
Practice End
比较综合的两道题目，笔者并不是很会这两道题的所有步骤，因此只会把关键步骤写出来。
- Codeforces 1182F Maxinum Sine 将题目要求的东西转化为 |2px \bmod 2q-q| 的最小值之后，进行二分，二分的 check 需要类欧，最后要用 exgcd 解，比较综合的题。
- Codeforces 1098E Fedya the Potter 运用双指针框定区间，然后二分，仍然是 check 函数里需要运用类欧。
Reference
- OI-Wiki 类欧几里得算法。
- AThousandMoon CF1182F 的题解。