数论-最大公约数和最小公倍数

声明

部分代码源于《数学一本通》by东南大学出版社

定义

就是最大的那个公约数呗
我们来个稍微学术点的定义:
一般地,设$a_1,a_2,…,a_k$是k个非零的整数,如果存在一个非零整数$d$,使得$d|a_1,d|a_2,…,d|a_k$,那么我们就说$d$是$a_1,a_2,…,a_k$的公约数。在公约数的集合里最大的,就是最大公约数
最小公倍数就是一般地,设$a_1,a_2,…,a_k$是k个非零的整数,如果存在一个非零整数$d$,使得$a_1|d,a_2|d,…,a_k|d$,那么我们就说$d$是$a_1,a_2,…,a_k$的公倍数。在公约数的集合里最小的,就是最小公倍数

最大公约数

最大公约数,一般表示为$gcd(…)$,数学上一般表示为$(…)$。这是显然肯定有的,至少是1。当$gcd=1$的时候,就说明这几个数是互质的。(区别于两两互质)。
下面介绍几种计算两个数的$gcd$方法。

欧几里得算法

欧几里得算法就是我们熟悉的辗转相除法(辗转相减法的 改进)。

原理

$gcd(x,y)=gcd(y-x)$

数论-同余

定义

同余,就是两个整数$a,b$对同一个整数$p$进行模运算,所得的余数相同,那么说这两个整数$a,b$关于$p$同余。
我们能够发现,

数论-整除

整除是数论中的基础知识。
【flag】博主想要写一套数论整合博客,此博客是第一篇。

声明

本系列博客中提到的数都是整数,

树的dfs序 整合

定义

dfs序是指:每个节点在dfs深度优先遍历中的进出栈的时间序列。
所以它有什么用呢
我们知道,树是一种非线性的数据结构,它的一些数据调用肯定是没有线性结构来得方便的。所以这个时候,dfs站了出来。基于dfs函数,我们可以在遍历的同时记录下每个节点进出栈的时间序列。就假设有这样一颗树:
你瞅啥
dfs序就是: