清北7日游（2）
Day 2:
上午数论
-
欧几里得算法 ：
gcd(a,b) = gcd(b,a \backslash b) -
证明 :
设 :
a,b 的最大公约数为c a=nc\ ,\ b=mc $ , $(n,m \in Z)$ , $a=k\times b + r r=a\%b=a-k b=nc-kmc=(n-km)c 若要使
(a,b) = (b,a\%b) ,则需要证 :
b , r 的最大公约数也为c ,用反证法 , 设存在 $ d $ 为 $m,(n-km)$ 的最大公约数，且 $d > 1$。 设 : $ n-km=qd $ , $m=pd 则
b = mc = pdc\ ,\ a=kb+r=kpdc + qdc=dc(kp+q) 则
a 还存在一个因数dc > c 此结论与
a,b 的最大公约数为c 相矛盾故不存在
d>1 作为m,(n-km) 的最大公约数则
m,(n-km) 互质 ，子证明成立。得:
b=mc , r=(n-km)c 中 ,m,(n-km) 互质 。则：
b 与r 的最大公因数仍为c -
gcd(n,m)·lcm(n,m) = nm
-
-
扩展欧几里得算法：简称
exgcd 一般用来求解不定方程，求解线性同余方程，求解模的逆元等，这里只介绍第一种，后两种在模/同余中会提到-
证明 :
-
①
ax_1+by_1=gcd(a,b) ②bx_2+(a\%b)y_2=gcd(b,a\%b) ③gcd(a,b)=gcd(b,a\%b) . 联立①②③与⑨可以得到ax_1+by_1=bx_2+(a\%b)y_2 -
a\%b=a- \left\lfloor\dfrac{a}{b}\right\rfloor b$,所以$gcd(a,b)=gcd(b,a- \left\lfloor\dfrac{a}{b}\right\rfloor b) -
化简：
ax_1+by_1=bx_2+(a- \left\lfloor\dfrac{a}{b}\right\rfloor b)y_2 ax_1+by_1=bx_2+ay_2- \left\lfloor\dfrac{a}{b}\right\rfloor by_2 ax_1+by_1=ay_2+b(x2-\left\lfloor\dfrac{a}{b}\right\rfloor y_2) 所以有
x_1=y_2,y1=x2-\left\lfloor\dfrac{a}{b}\right\rfloor y_2 ,至此，递归关系已非常明了。 -
通解 ：通过以上方法可以得到一解
x_0,y_0 ,然后可得通解：x=x_0+\dfrac{b}{gcd(a,b)}\times t,y=y_0+\dfrac{a}{gcd(a,b)}\times t,t \in Z
此时\dfrac{b}{gcd(a,b)},\dfrac{a}{gcd(a,b)} 为最小系数 -
求解不定方程:
-
对于不定方程 :
ax + by = c ,根据 扩展欧几里得 :- 1.若
c \% gcd(a,b) \not= 0 , 则原方程无解
2.若
c \%gcd(a,b) = 0 设
d = gcd(a,b) , 则原方程可转化为 :a\times (x\times \frac{d}{c}) + b\times (y\times \frac{d}{c}) =d (= c\times \dfrac{d}{c}) 用
exgcd 可以求出当ax+by=d 时的解，再使x,y 分别乘上\dfrac{d}{c} , 即可得到原方程ax + by = c 的解 - 1.若
-
-
逆元 ：
x·inv(x) \equiv1(mod\;p) -
当且仅当
p 为质数时，根据费马小定理 ,可得 :inv(x)·x \equiv x^{p-1}(mod\;p) 所以 ：
inv(x)\equiv x^{p-2}(mod\;p) -
证明: 移项得：
x^2-1 \equiv 0(mod \; p) ，根据平方差公式可得:(x+1)(x-1) \equiv 0(mod\;p) ,所以(x+1)|p 或(x-1)|p -
求解模的逆元
-
扩欧法：
由基础知识可知关于
x 和它的逆元inv(x) 在mod\ b 意义下的关系：x·inv(x)\equiv 1(mod\;b ) ,可近似的看作一个同余方程求解 -
费马小定理法：
需要用到快速幂
-
递推法：
- 设
p=k\times i+r
因为
p\equiv0(mod\;p) ，所以k\times i+r \equiv 0(mod\;p) - 设
方程两边同乘
(inv(i)\times inv(r)) 可得：$ k\times i \times inv(i)\times(inv(r)+r\times inv(i)\times inv(r) \equiv 0(mod\;p)$k\times inv(r)+inv(i)\equiv 0(mod\;p) inv(i)\equiv-k\times inv(r)\;(mod\;p) $inv(i)\equiv -\left\lfloor\dfrac{p}{i}\right\rfloor\times inv(p\%i)\;(mod\;p)$至此，递推关系明了，设置边界$ inv(1)=1$,并且为了保证为正整数解，则需要再加上$p$,因为最后要$\%p$，所以可以保证正确性 关系式：$ inv[i]=(p-p/i)*inv[p\%i]\%p$-
阶乘法：
inv(i)=\dfrac{1}{i!}*(i-1)!
-
下午数据结构：
-
-
-
-
-
-
6.trie -
7.hash -
8.RMQ / LCA
堆：
-
定义
\&\& 功能：- 结构：满二叉树
- 最大堆/最小堆
- 以最大堆为例
- 有查询最大值、插入、删除最大值三种操作
-
操作：
-
插入：
-
插入其实就是把插入结点放在堆最后面，然后与父亲比较，如果父亲值小于它，那么它就和父亲结点交换位置，重复该过程，直到插入节点遇到一个值比它大的父亲或者它成为树根结点
-
删除：
-
删除就是删除最大堆中的最大值或者最小堆中的最小值，也就是树根
-
以删除最大堆树根为例子，删除其实就是整个堆中少了一个结点，不妨把位于最后面的一个结点当成新的树根，然后与它左右孩子比较，与值最大并且值大于它的孩子进行交换（好好读这句话），直到它的孩子都是小于它的，或者变成树叶
-
二叉搜索树：
-
定义
\& \& 功能：- 递归定义
- 它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。
- 满足性质：结点u的左子树的结点权值都比u小，右子树的结点权值都比u大。
- 插入、删除、查找只需在二叉树中按照权值往下走即可。
-
缺点：
- 可能退化成一条链（例如如果按升序插入），那么每次操作平均复杂度O(n)
-
补足：
-
Splay
-
线段树：
-
定义
\&\& 功能：- 维护区间信息的数据结构
- 每个结点对应一个序列的区间
- 完全二叉树，左子树为左一半区间，右子树为右一半
- 单点/区间修改。
-
缺点：
- 空间浪费
-
补足：
-
动态开点：
-
每个结点的值表示对应区间内的数的个数
-
每次操作至多增加
O(logn) 个非零结点 -
我们只需要将这
logn 个非零结点开出来即可，空间复杂度O(nlog(inf)) -
查询时，如果碰到没有开出的结点，说明这个结点值为
0 ，返回0 即可 -
注意：
-
注意此时不能使用数组模拟二叉树的方法（和堆类似，
1 为根，2n - 1 和2n 分别为n 的左右儿子） 因为得开10^{9} 的数组，爆空间
-
-
得加上左右儿子指针的数组。
- 为新开的结点赋予大于零的编号
o=++tot;
- 为新开的结点赋予大于零的编号
-
查询时遇到结点编号为
0 ，就说明这个结点为空，对应区间中没有数 -
动态开点线段树的合并：
tree *merge(int l, int r, tree *A, tree *B){
if(A == NULL) return B;
if(B == NULL) return A;
if(l == r) return new tree(NULL, NULL, A -> data + B -> data);
int mid = (l + r) >> 1;
return new tree(merge(l, mid, A -> ls, B -> ls), merge(mid + 1, r, A -> rs, B -> rs), A -> data + B -> data);
}
//复杂度：两棵线段树中重合结点（对应位置都开出来的结点）的个数。
树状数组:
-
定义&&功能：
-
支持单点修改，查询前缀和。
-
复杂度
O(logn) ，常数小
-
-
重要思想:
-
lowbit( x ) = x \& - x - 取出
x 最右边的1 和它后面的0 组成的数
-
-
优点:
- 可扩展性好
-
缺点:
- 只能维护满足可减性的量
e.g. 和、异或和，与、或这类不满足可减性的量则不能用树状数组维护。
- 只能维护满足可减性的量