Loi_Vampire's Blog

自己选择的路,就算跪着也要走完

03/22
14:29
学习笔记 数论

数论学习笔记

好久之前的草稿了QAQ

放出来吧,还没写完,先挖个坑吧放着吧 (虽然不知道还填不填的完)

一、筛法

先从最基本的筛法开始吧

1. 埃式筛

时间复杂度 O(nloglogn)

2. 线性筛

时间复杂度 O(n) 可以用来筛积性函数

每个合数只会被它最小的质因数筛去,保证了时间复杂度

二、一些积性函数

对于一个定义域为{N^ + }的函数f,如果对于任意两个互质的正整数ab,都满足f(ab) = f(a)f(b),则称函数f为积性函数。如果对于任意两个正整数ab 都满足f(ab) = f(a)f(b)的话,则称函数f为完全积性函数。

1.欧拉函数

\varphi \left( n \right) 表示1…n中于n互质的数的个数,这是一个积性函数,具体证明涉及中国剩余定理。

\varphi 函数的取值:

对于一个素数p,自然想到\varphi \left( p \right) = p - 1

对于一个素数pk次方,\varphi \left( {{p^k}} \right) = {p^k} - {p^{k - 1}},也很好证明:

1...{p^k} 中,与 {p^k} 不互质的有 1*p,2*p,3*p ... {p^{k - 1}}*p{p^{k-1}} 个,所以于 {p^k} 互质的数共有 {p^k} - {p^{k - 1}}

对于一个合数n必定能拆成多个质数的乘积的形式,所以\varphi \left( n \right) = n\Pi \left( {1 - \frac{1}{{{p_i}}}} \right)。证明:

\varphi \left( n \right) = \varphi (\Pi p_i^{{a_i}}) = \Pi \varphi \left( {p_i^{{a_i}}} \right)

之前证明得到\varphi \left( {{p^k}} \right) = {p^k} - {p^{k - 1}},变形得到\varphi \left( {{p^k}} \right) = {p^k}\left( {1 - \frac{1}{p}} \right),所以\varphi \left( n \right) = \Pi p_i^{{a_i}}\left( {1 - \frac{1}{{{p_i}}}} \right) = n\Pi \left( {1 - \frac{1}{{{p_i}}}} \right).

线性筛筛欧拉函数时

对于一个合数n有两种情况:

1.n = p * {\rm{i}},且Gcd(p,i) = 1,根据积性函数的性质\varphi \left( n \right) = \varphi \left( p \right)\varphi \left( {\rm{i}} \right)

2.n = p * {\rm{i}},且素数p是i的一个因数,\varphi \left( n \right) = p * {\rm{i}}\Pi \left( {1 - \frac{1}{{Pi}}} \right) = p\varphi \left( {\rm{i}} \right)

2.莫比乌斯函数

  • \mu(n)=\begin{cases}&1 & \text{ if $n$ = 1}\\&(-1)^k & \text{else if $n={p_1}{p_2}{p_3}...{p_k}$}\\&0 & \text{else}\end{cases}

  • {\Sigma _{\left. d \right|n}}\mu \left( d \right) = \left[ {n = 1} \right]

所以用线性筛筛莫比乌斯函数的时候:

对于一个素数p,明显\mu \left( p \right) = - 1

对于一个合数n = p * {\rm{i}},且pi的一个因数,可以想到\left. {{p^2}} \right|n,所以\mu \left( n \right) = 0

对于一个合数n = p * {\rm{i}},且p不是i的一个因数,所以n的质因数的个数比i多1,\mu \left( n \right) = -\mu\left( {\rm{i}} \right)

 

01/5
21:35
图论 学习笔记

LCT学习笔记

什么是LCT?

LCT:link-cut-tree 动态树 用来维护树或者森林

在LCT中引用了轻重链的思想,有这么几个概念:

  • Preferred Child 偏好子节点
  • Preferred Edge 偏好边
  • Preferred Path 偏好路径
  • Auxiliary Tree 辅助树

例如:

根节点1的preferred child是2,那么边1-2是一条preferred edge,2的preferred child是6,那么从节点1到节点6的路径是一条preferred path。 3、4、5、6没有preferred child。

1-2-6就被拆成了一条链,3、4、5各自是一条链。

那么什么是Auxiliary Tree(辅助树)呢?

Auxiliary Tree 是将这些链上的节点以深度为关键字而建成的一颗颗splay树。

就拿刚才的例子来说,它的Auxiliary Tree就是:

这里还有一个概念就是 Path Parent 路径父节点,即一条树链组成的splay的根节点与另一棵splay树连接的节点。如3节点的Path Parent 是1节点。

这样再用数据结构来加速的话,时间效率能达到log 级,貌似这也是树链剖分的原理。

LCT的基本操作

一、Access(访问)

Access操作称得上是LCT所有操作的基础。如果access了某个节点,则该节点到根节点上的所有节点都变成了preferred child,所有的边都变成了 preferred edge,这条路径也变成了 preferred path。而这条树链就加入了根节点的Auxiliary Tree中。

具体操作:将访问的点splay到Auxiliary Tree根的位置,然后断开右儿子(因为被访问的点没有 preferred child);然后访问它的Path Parent,将其splay到Auxiliary Tree根的位置,断开右儿子,连到访问的节点上,一直重复这个过程。

还是之前的那棵树,看一下access(3)过程中的变化:

初始的Auxiliary Tree:

将3节点splay到根的位置,断开右儿子,没什么变化……

然后访问3节点的Path Parent 1节点,将其splay到根的位置,断开右儿子,并与3节点连接。变化如下:

原树变化如下:

二、Makeroot(换根)

只需access(x),splay(x),再反转就好了。

先将u节点splay到根的位置,然后将u的Path Parent设为v即可。

四、Cut(拆分)

先将u节点splay到根的位置,然后access(v),splay(v),再断开u与v的联系即可。

LCT中splay的写法注意

一、isroot()

一般splay的写法,判断一个节点是不是根节点只要看它的父节点是不是NULL即可。

而在LCT中,因为涉及多棵splay树,一棵splay树的根节点可能连向另一颗splay树。

二、rotate()

三、splay()

就先到这吧…