类欧几里得算法,简称类欧,因为计算过程中有类似辗转相除的算法故叫类欧几里得算法。

前置知识

  • 欧拉定理 / 欧拉函数
  • 取模
  • 限制转换
  • 简单的不等式知识
  • 放缩
  • 平方化简公式(具体见化简 $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
  • 写这篇文章的目的:纪念我的第一道黑题(类欧模板)
  • 最后:感谢阅读,有什么问题欢迎指出
分类: 文章

Shuchong

菜鸡书虫

2 条评论

Shuchong · 2020年7月20日 3:07 下午

欢迎大佬纠错 /kel

Sora1336 · 2020年7月20日 2:02 下午

% 书虫

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注