类欧几里得算法，简称类欧，因为计算过程中有类似辗转相除的算法故叫类欧几里得算法。
前置知识
- 欧拉定理 / 欧拉函数
- 取模
- 限制转换
- 简单的不等式知识
- 放缩
- 平方化简公式（具体见化简 $f_2$ 那个模块）
模板题：P5170【模板】类欧几里得算法
基础
给定一个函数
$$f(n,a,b,c)=\sum\limits_{i=0}^n\left\lfloor\dfrac{ai+b}{c}\right\rfloor$$
和 $n,a,b,c$，求 $f(n,a,b,c)$。
我们看到 $n \le 10^9$，所以直接暴力加上 $t \le 10^5$ 直接死掉，所以我们要用一种 $O(\log n)$ 的算法。
所以，不能暴力，这个函数该怎么计算呢 qwq
我们可以换一种想法来理解这个 $\sum$。
假设今天小 S 去打工，老板说只要他能让这个商店的营业满足 $0 \le i \le n$ 的条件，那么就给他的工资进行
$$\left\lfloor\dfrac{ai+b}{c}\right\rfloor$$
的贡献。（老板说 $a,b,c$ 是一个常数，不会变的 除非小 S 偷懒，但小 S 不会偷懒的）
小 S 不傻，他觉得每天都要满足这个条件太麻烦了，所以他要把工资进行 合并。
但是这个合并有点麻烦，所以他跟老板说：
“我可以把工资和条件进行转化吗？”
通（man）情（heng）达（wu）理的老板同意了。
所以这样的工资通过 和条件转化 的合并方式，就可以得到下面的式子：
$$\texttt{原式}=\sum\limits_{i=0}^n\sum\limits_{j=0}^{\left\lfloor\frac{ai+b}{c}\right\rfloor-1}1$$
老板数学不好，看到这个式子吓蒙了，准备解雇小 S ……
小 S 赶紧说：
“啊别别别，我知道这个式子很麻烦，您是不是觉得 $j$ 很麻烦啊？”
“w，是的”
所以这该咋办呢 qwq
小 S 问了博学多才的学长小 C，他说：
“教你个东西，叫做 限制转换，算 $i$ 不好算，就算 $j$，用 $n$ 来 强度 限制 $j$。”
小 S 懂了，于是有了下面的限制式子：
$$\texttt{原式}=\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\sum\limits_{i=0}^n\ (j<\left\lfloor\dfrac{ai+b}{c}\right\rfloor)$$
stop，现在我们来捋一捋我们推导的过程。
$$\sum\limits_{i=0}^n\left\lfloor\dfrac{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\ (j<\left\lfloor\dfrac{ai+b}{c}\right\rfloor)$$
现在，$i,j$ 都被 $n$ 所限制了，下面我们来做一些化简。
（小 C：“这个在 OI 界的学术名词叫做 放缩。”）
First，我们尝试 去掉下取整（主要靠的是不等式的小技巧）
$$j<\left\lfloor\dfrac{ai+b}{c}\right\rfloor\to j+1 \le \left\lfloor\dfrac{ai+b}{c}\right\rfloor \to j+1 \le \dfrac{ai+b}{c}$$
（这里运用了简单的不等式知识，如果看不懂的话建议看一看七年级下《不等式与不等式组》）
Second and Third，变换后再次下取整（为了体现这是两步所以我分行隔开了）
$$\texttt{原式}\to jc+c \le ai+b \to jc+c-b-1 < ai\ (\text{This is Second})$$
$$\texttt{原式}\to \left\lfloor\dfrac{jc+c-b-1}{a}\right\rfloor<i\ (\text{This is Third})$$
小 S 跟这小 C 的思路化简到了这里，小 S 不明白化简到这里有什么用处。
小 C 说：“你试试，可不可以通过推导把 $i$ 消掉？”
小 S：“/yiw 我试试吧”
$$\texttt{原式}=\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}n-\left\lfloor\dfrac{jc+c-b-1}{a}\right\rfloor=n\left\lfloor\dfrac{an+b}{c}\right\rfloor-f\left(\left\lfloor\frac{an+b}{c}\right\rfloor,c,c-b-1,a\right)$$
哇！这变成一个递归的模式啦！
就这样，我们搞出了类欧的 $O(\log n)$ 的算法。
拓展
给定两个函数
$$f_1(n,a,b,c)=\sum\limits_{i=0}^ni\left\lfloor\dfrac{ai+b}{c}\right\rfloor$$
$$f_2(n,a,b,c)=\sum\limits_{i=0}^n\left\lfloor\dfrac{ai+b}{c}\right\rfloor^2$$
和 $n,a,b,c$，求 $f_1(n,a,b,c)$ 和 $f_2(n,a,b,c)$。
按照上面的方法，我们逐一进行化简。
（为了方便，$k_1=\left\lfloor\dfrac{an+b}{c}\right\rfloor$，$k_2=\left\lfloor\dfrac{ai+b}{c}\right\rfloor$，$k_3=\left\lfloor\dfrac{jc+c-b-1}{a}\right\rfloor$）
最后你会发现都可以递归的！
$f_1$ 化简
$$\begin{aligned}\texttt{原式} & =\sum\limits_{j=0}^{k_1-1}\sum\limits_{i=0}^n\ (j<k_2)\ i\\& = \sum\limits_{j=0}^{k_1-1}\sum\limits_{i=0}^n\ (i>k_3)\ i\\& = \sum\limits_{j=0}^{k_1-1}\sum\limits_{i=k_3+1}^n\ i\\& =\sum\limits_{j=0}^{k_1-1}\sum\limits_{i=1}^n\ i\ -\ \sum\limits_{i=1}^{k_3}i\ \ \\&=\sum\limits_{j=0}^{k_1-1}\dfrac{1}{2}n(n+1)\ -\ \dfrac{1}{2}k_3(k_3+1) \\& =\dfrac{1}{2}\left[k_1n(n+1)-\sum\limits_{j=0}^{k_1-1}k_3^2-\sum\limits_{j=0}^{k_1-1}k_3\right]\\& =\dfrac{1}{2}[k_1n(n+1)-f_2(k_1-1,c,c-b-1, a)-f(k_1-1,c,c-b-1,a)]\end{aligned}$$
$f_2$ 化简
首先记住一个公式：
$$\text{MF}^2=2\dfrac{\text{MF}(\text{MF}+1)}{2}-\text{MF}=\left(2 \sum\limits_{i=0}^\text{MF}i\right)-\text{MF}$$
（小 C：“不要问为什么，记住他就可以 /xyx”）
$$\begin{aligned}\texttt{原式}&=\sum\limits_{i=0}^n\left[\left(2\sum\limits_{j=1}^{k_2}j\right)-k_2\right]\\&=\left(2 \sum\limits_{i=0}^n\sum\limits_{j=1}^{k_2}j\right)-f(n,a,b,c)\\&=\left[2\left(\dfrac{1}{2}nk_1(k_1+1)-\sum\limits_{j=0}^{k_1-1}(j+1)k_3\right)\right]-f(n,a,b,c)\\&=nk_1(k_1+1)-2f_1(k_1-1,c,c-b-1,a)-2f(k_1-1,c,c-b-1,a)-f(n,a,b,c)\end{aligned}$$
总和
最后的结果是要求 $t$ 组 $f,f_1,f_2$，我们发现这三个函数都有互相的递归，复杂度也需要 $O(\log n)$，所以代码要写在一个函数里。
拓展 $\times\ n$
接下来就是一些练习题啦 ~
在你谷貌似没有发现特别经典的题目，因为是较近的算法，所以题目较少。
特别鸣谢
- OI-Wiki 类欧几里得算法
- 卢本伟！TA 指出了这篇博客的错误
- 友情出演：
- 小 S：书虫
- 小 C：ClCN
- 写这篇文章的目的：纪念我的第一道黑题（类欧模板）
- 最后：感谢阅读，有什么问题欢迎指出
2 条评论
Shuchong · 2020年7月20日 3:07 下午
欢迎大佬纠错 /kel
Sora1336 · 2020年7月20日 2:02 下午
% 书虫