两边一除就得到了

☝我们想用这个性质来判断一个数是不是质数，有没有搞头。
所以我们给出下面的伪代码

看起来很有道理，但实际上是有问题的。问题出在费马小定理不是充分必要的。
比如 : $341 = 11 \times 31$，但是 $2^{340} \equiv 1 \pmod{341}$，是不满足的。
所以我们希望：对于一个合数，绝大部分的a还是会满足这个条件，也就是反例没有很多。
很可惜，存在一类数比较有个性。Carmichael numbers。
所有与N互质的a都满足

$561=3\times 11 \times 17$就是一个典型的Carmichael number。

我们先不管Carmichael number，先对non-Carmichael number研究。
我们先引入一个Lemma：
如果一个与N互质的a满足

则小于N的a(互质数)里至少有一半a满足上面这条。
简短的证明：
如果存在

则

对每个骗子b，我们都至少有一个 ab mod N是老实的，所以老实的至少和骗子的一样多。所以至少有一半a满足。

我们现在忽略Carmichael number，那么我们连挑k个小于N的a，用上面的伪代码检验。
如果我们没找到a使得 $a^{N-1} \not\equiv 1 \pmod{N}$，
那么如果N是质数，我们判断是百分之百对的。
如果N是合数，我们判断失误的概率是$\leq\frac{1}{2^k}$（因为每次挑到骗子的概率是小于 $\frac{1}{2}$ 的。

我们想用这一套算法来造随机质数
接下来我们引入一个Lagrange’s prime number theorem
$\pi(x)$ 表示不大于x的素数个数，那么有：

更精确的说：

然后再根据以上的素性检验，我们有一套造随机质数的算法：

1. 随机选一个n比特数
2. 跑素性检验
3. 过了就输出，没过就重复

那么这个算法跑的快不快呢，我们来分析一下：
每次选一个随机的n比特数，选中质数的概率是：

所以大概选个$O(n)$轮就差不多了。

密码学：
考虑场景：我想把一串字符发给另一个人，但是我发送过去的消息可能被截取，所以我们想要对字符进行加密。

Private-key schemes: one-time pad
我们两个私下见了一次面，确定了一串和发送消息等长的字符，这样我发送的时候用这串字符异或一次，消息到对面了他再用这串字符异或一次，就得到了原文。

这样非常的安全，对面穷举也很难破解。但是我们的开销也很大：我们需要预共享海量的加密用字符，成本极高，所以我们需要引入公钥.

Public-key Cryptography：
我的目标就是：我留一串公钥在网上，谁都能用这个公钥加密，但是只有我能用我的私钥解密。
一个经典的加密方法：RSA（Rivest-Shamir-Adelman）
我们挑两个质数p, q,令 N = pq，我们就可以取任意一个与(p-1)(q-1)互质的e作为公钥，再在取e在模(p-1)(q-1)意义下的乘法逆元作为私钥。
我们首先区分：网络上大家都能看到e和N，但是不知道d。这个加密成立的前提是我们认为质因数分解是困难的，也就是我们很难快速分解找到p和q进而得到d。
加密：我把要发送的信息 $x$ 变成 $x^e$ mod N，发送给对面
解密：对面用 $(x^e)^d$ mod N 计算就得到 $x$
说明一下正确性：
首先我们有：

所以 $ed$ 可以写成：

所以有：

由于 $p$ 是质数，所以

所以

同理，对q也成立。所以 $N |\text{(}x^{ed} - x$ mod N)。进而得到

全域哈希：
我们有250个客户，每个客户有一个ip地址，我想为每个ip地址标注上客户的名字，但是ip地址有$2^{32}$ 种可能性。我们自然也可以写一个250个if else，但是这样每次寻找名字的复杂度都是 $O(n)$。
一个想法是：我们寻找一个哈希函数，把每个ip地址映射到一个250个元素的表里。这样我们每次拿到ip地址做一次映射就能找到对应的名字了。
但是哈希函数常有冲突，所以实际上我们实现的时候每个元素其实是个桶，每次进入一个ip地址我们扔进这个桶里，查找时先应用哈希找桶再在桶里找，可以显著降低时间消耗。
但是，没有一个哈希函数是适用于所有情况的，我们总能找到一组奇异的数据来使得我们的哈希退化到 $O(n)$ 。所以我们的解决方案是：我们从某类函数中随机选一个函数作为我们的哈希函数。
比如有一个ip地址 $x = (x_{1},x_{2},x_{3},x_{4})$，我们随机挑一组数$(a_{1},a_{2},a_{3},a_{4}) \in [0,n-1]$，计算哈希函数为：

这样两个ip地址哈希冲突的概率就是 $\frac{1}{n}$。

Chapter 2. Divide-and-Conquer Algorithms

分治算法的主体思路：

1. 把问题分成几个子问题
2. 解决子问题
3. 合并子问题

乘法：
我们知道乘法运算的时间复杂度是比加法高一个量级的。所以我们下面讨论复杂度的时候仅讨论乘法即可。
我们想要计算 $(a+bi)(c+di) = ac-bd+(bc+ad)i$，那么要经过4次乘法运算。
但是我们发现：$bc+ad = (a+b)(c+d)-ac-bd$，这样我们只用进行3次乘法运算即可。
我们接下来将阐述如何用这个思路简化整数的乘法运算。
考虑整数 $x \times y$
我们认为$x,y$是两个n比特数，其中n是2的次方。（不够的话补0就行了）
我们把$x,y$换成2进制表示。分别截取前 $\frac{n}{2}$ 位和后 $\frac{n}{2}$ 位得到 $x_{L}, x_{R},y_{L},y_{R}$，由二进制定义易知

于是乎，我们就有

有加法和乘以2的次方都是线性的（直接在后面加0就行了）
我们记 $T(n)$ 为n位输入下要跑的时间，那对于乘法，就能写出：

运用后面会学的主定理我们可以解出 $T(n) = O(n^2)$

那我们在这里运用一下上面提到的4次乘法变3次的技巧：
给出伪代码：

此时有递推关系：

可以解出 $T(n) = O(n ^{\log_{2}3})$

递推关系：

Master theorem（主定理）
如果有：

那么我们将得到：

简要证明：
我们先考虑这个式子的含义：我们把一个问题分成了b个子问题，在合并子问题的时候做了a次操作。所以这棵树的高度为 $\log_{b}n$。
我们现在考虑第k层所用的时间：
合并子问题的操作数为 $a^k$，每个子问题的规模是 $\frac{n}{b^k}$，每个子问题的代价是$O\left( \left( \frac{n}{b^k} \right)^d \right)$
故每一层的代价是

总时间就是求和：

这是个等比数列求和，再对3种大小关系讨论一下就得到主定理了。

归并排序：
我相信你的程序设计课肯定学了这个，这里就不赘述了。
值得注意的是我们在这里讲到了强比较算法的时间下界。
我们可以把一个排序写成一棵决策树，每个叶子节点表示一个排列，每个内部节点表示一次比较，每条边表示这个节点是否为真从而导入下一个节点。对于一个序列，排好序的状态有 $n!$ 种，所以这棵二叉决策树的高为 $\log(n!) = O(n\log n)$，所以基于比较的排序有 $O(n\log n)$ 的下界。
而部分不依赖比较的排序方法，比如基数排序和桶排序，在某些数据下可以打破这个下界。作业中会看到。

中位数：
一个朴素的想法：直接排序找中间就行。预期复杂度是 $(n\log n)$ 。但是我们只想要中位数，不需要两两之间的大小关系，所以我们有希望把这个算法降成线性的。
我们采用以下算法：
我们随机选取v。
对于每个v，把这组数分成3组：小于v的，等于v的和大于v的。判断v是否是中位数即可。
理想情况下，小于v的和大于v的都大概在 $\frac{n}{2}$ 左右，我们能写出以下递推公式：

故而预期时间复杂度是线性的。
然而呢，最坏情况下，我每次都选到边界，导致算法会退化到 $O(n^2)$。
那么现在我们这个算法的平均预期复杂度是多少呢？还是线性的。
给出一个简短的证明：
我们认为选取到的v在25百分位数和75百分位数之间是好的选取。
一次好的选取的概率是 $\frac{1}{2}$，故预期每两次就能得到一次好的选取。
故有：

从而得到是线性的。

矩阵乘法：
显然一个朴素的矩阵乘法是 $O(n^3)$ 的。
对它使用分治吧！

每次需要计算AE,BG,AF,BH,CE,DG,CF,DH，并做一次 $O(n^2)$ 的加和。
有递推公式：

算出来仍是 $O(n^3)$ 的
然而，有人惊人的注意到，倘若我们这样算，居然只用作7次子矩阵乘法

其中

这样我们就有递推公式：

进而由主定理得到 $T(n)=O(n^{\log_{2}7})$

快速傅里叶变换(FFT)：
FFT是加速卷积（多项式乘法）的一个算法。（是翌佳最爱的算法之一）
我们考虑现在有两个序列：

其中

算这个的时间复杂度是 $\Theta(d^2)$的。
我们注意到，一个d次多项式的表示方法其实有两种。我们除了可以写出d+1个系数外，还可以由这个多项式的d+1个点来确定。（类似于两点确定一条直线）。
那么我想要确定 $C(x)$ 的所有系数，我需要找到 2d+1 个点在 C 上的取值。
因此，我们引入了fft与ifft，快速求值与快速插值。
简单来讲，我们通过fft快速求出A，B分别在 2d+1 个点上的取值，然后我们把这些点逐点相乘就得到了 C 在 2d+1 个点上的取值。最后我们通过ifft用 C 在这 2d+1 个点上取值的快速还原 C 的各个系数。这就是大致思想，我们接下来介绍如何快速求值和快速插值。
我们接下来给出一般性的fft，所以我们不妨假定n是2的幂次（不够补到就行了）
我们选择n个点：

我们先把 $A(x) = a_{0} + a_{1}x + \dots + a_{n}x^n$拆一下，得到：

这样拆有什么好处呢？注意到我们选择的这n个点正负两两配对，所以有

也就是说我们只要算出 $A_{e}(x^2)$ 和 $A_{o}(x^2)$ 就能得到这两个点。我们就成功的把这个问题分治成了两个子问题。那我们随便挑一个来看，看到 $A_{e}(x^2)$，我们拥有的点是：

那我还是想让这 $\frac{n}{2}$ 个点两两正负配对从而实现分治，为了使平方数仍然有正负配对，所以我们引入虚数作为点的选择。
选取

的n个单位根: $1,\omega,\omega^2\dots \omega^{n-1}$,其中 $\omega = e^{\frac{2\pi i}{n}}$
由单位根性质，$\omega^{j+\frac{n}{2}} =-\omega^j$,每次就取正的$\omega^{1\to \frac{n}{2}-1}$平方，原来差 $\frac{\pi}{4}$ 的平方之后又差 $\frac{\pi}{2}$ ,又形成了正负配对。进而我们成功把这个问题不断递归下去，直到只有一个点（经过n次平方，取到1）的时候，我们就直接计算即可。
给出伪代码：

不难发现：

故得到fft的时间复杂度为 $O(n\log n)$

接下来考虑如何通过ifft把取值还原成系数。
我们通过fft算出A在n个单位根的取值了对吧，那我们可以写成：

令

则有：（挺显然的）

那么我们把fft得到的结果作为输入，再以 $\omega^{-1}$为单位根做一遍fft最后除以n就得到了原来的系数。

逆序对：
程序设计课肯定讲了，不再赘述。

Chapter 3. Decompositions of graphs

两种存储方式：邻接表与邻接矩阵

DFS： 程序设计课一定学过。
我们引入一些dfs的概念：
我们定义一个节点的pre：第一次走到这个点的时间
post：完成这个点的时间（即最后一次来到这个点）
首先是无向图中的：

1. 树边：dfs树上的边
2. 回边：剩下的边

有向图中：

1. 树边：dfs树上的边
2. 前向边：一个节点指向非子节点的后代的边
3. 回边：一个节点指向祖先的边
4. 交叉边：指向一个已完成的点（即两个子树间相连的边）

我们考虑用一条边两个节点的(pre,post) (u->v)来判断这条边的类型
$[_{u} [_{v} \quad ]_{v} ]_{u}$ :树边\前向边
$[_{v} [_{u} \quad ]_{u} ]_{v}$ :回边
$[_{u} ]_{u} \quad [_{v}]_{v}$ :交叉边
如果找到一条回边那么这个图就有环。

拓扑排序(Linearization/Topologically Sort)：
这是针对DAG的算法。我们的目的是使得每条边都从序数较小的点去到序数较大的点。
我们定义两个概念：sink：无出边；source：无入边。
我们每次找到一个source，记录并删去它，重复直到图为空。

强连通分量(Strongly connected components\SCC)：
定义强连通分量：在该子图里任意两点u,v均存在u->v的路径与v->u的路径
任何有向图都能转换成其强连通分量的DAG(如果有环，那环上的就不是强连通分量，可以把整个环合成强连通分量)

如果我们从一个点u出发开始找（dfs就行），那么它应该在把u可达的所有节点跑完后终止。
如果一个节点在sink scc中，那么从这个节点开始跑，得到的最终结果就应该是sink scc。（从定义出发不难理解）
那么我们现在就有两个问题：
(a):我们如何找到位于sink scc里的节点
(b):找到了sink scc又如何找到下一个。

为解决这些问题，我们引入两个Lemma：

1. 如果 强连通分量C里有一个节点 有一条指向 强连通分量 C'里的节点（可以看做meta graph上C有一条边指向C')，那么C中最大的post值一定比C'里大。(可以考虑dfs的顺序，由于C指向C‘，则C一定在C’后完成，post值一定更大)。
2. post最大的点一定在source scc里（由1可知）

也就是说，我们一定知道source scc里的一个点，这与我们的问题(a)有点出入，于是我们考虑反图。
即我们把图G中所有的边反向得到图 $G^R$，首先，反图的强连通分量一定与原图相同，且原图的source scc就变成sink scc了。于是我们自然而然的就得到了以下线性算法：
在反图上跑一遍dfs得到post值，然后在原图上挑post值最大的没有遇到过的点为起点跑一次dfs。这样每次跑一遍dfs得到的点就是一个强连通分量。

Chapter 4. Paths in Graphs

bfs程序设计课上肯定也讲了。
Dijkstra’s algorithm：
我们知道，bfs可以找到边权为1的图中的最短路，如果边权不为1呢？
一个简单的想法：把边权不为1的边裁成若干个边权为1的边然后建虚点。很明显边权比较大的时候这是非常不妙的。
（待续。。。）

为什么dijkstra不能在负权图上使用呢？我们考虑下面这个图：
1->2 3
1->3 5
3->2 -3
那么以1为起点，用dijkstra可以到2的最短路是1->2是3，但是很明显，1->3->2为2更短。其原因在于：存在负边，则当前最小不一定是全局最小。
那对于含有负权边的图该怎么办呢，我们引入如下算法：
Bellman-Ford algorithm：
我们先引入一个松弛操作：
UPDATE(u,v):dist(v)=min(dist(v), dist(u)+l(u,v))
如果dist(u)是到u的最短路，且u是到v的最短路上的倒数第二个点，那么v的最短路也算出来了。
那么怎么才能保证以上这两点呢？我们松弛|V|-1次。
给出伪代码：

对第i次循环，dist(u)表示的是：从起点出发，最短路径不超过i条边的路径长度。因为每一轮松弛，我们只能保证最短路径小于i条边时的答案是对的。如果没有负环，那么最短路径最多经过|V|-1条边，所以循环|V|-1次就行了。
那么如果循环|V|次了，还有dist(u)在更新，这就说明，到这个点的最短路有|V|条边，那么一定存在负环。故这个算法也能用来检测负环。

DAG中的最短路：
可以直接类似动态规划，由于DAG中无环，所以我们按照拓扑排序的顺序一步步更新值即可。
给出伪代码：

在这个条件下最长路也可求：对每条边取负，求完最短路再取负即可。

Chapter 5. Greedy algorithms

Minimum spanning trees：
简单来讲，就是在一个图中，选出一棵覆盖所有节点的树，并使得其边权和最小。
我们引入Kruskal算法：简单来讲就是先把边排好序，挑出最小的边，如果这条边加入当前的树中不构成环，就加入，否则就下一条，直到加入 |V|-1条为止。
如何保证正确性呢？我们引入一个比较重要的Lemma： Cut Property
考虑X是MST的一部分，把图划分成包含X和不包含X的两部分（S与V\S)。那么取连接S与V\S两部分的最小的一条边e，$X \cap \{e\}$ 也是MST的一部分。还挺显然吧（），证明见讲义。大概思路就是如果$X \cap \{e\}$ 是MST一部分，那就不用证明；如果不是，我们就构造出一棵新树。具体操作就是已知是一棵连通的树，我们加入e，那就必须删除一条连接S与V\S两部分的那条边，不然就会有环，删除后也不影响连通性。此时边权和小于等于原来的边权和，故其一定是MST。

给出伪代码：

新的问题来了，我们的union和find应该怎么写才能保证能成功判断环呢？
我们采取按秩合并。（并查集）

可见我们最后大致把find转换成了在树形结构上寻找。此时每次操作的复杂度都是 $O(\log n)$。
有3个性质：

1. 如果x不是根，$rank(\pi(x))>rank(x)$（由定义可得）
2. 任何秩为k的点，子树大小至少为 $2^k$（归纳法易证）
3. 最多只有 $\frac{n}{2^k}$ 个的点的秩到达过k（作业会证）

因此，目前来讲，时间的瓶颈主要还是在
O(|E| log |V |) 来排序
O(|E| log |V |) 来union和find。
假使我们把边排好序了在输入，能不能优化呢，也就是说我们能不能优化我们并查集的复杂度。
我们引入路径压缩：

应用路径压缩，我们可以把原 $O(\log n)$ 的复杂度优化至接近常数。
简单来讲，也就是我们find时每次都把路上碰见的节点挂靠的根上，这样之后每次对它查找都快得多。
以下是对路径压缩后的并查集复杂度的证明：
我们把n划分到以下区间：

区间个数为 $\log^ n$，定义为n连续取log最后小于1的次数。
一旦一个点不是根了，其秩就固定了，我们为其发放$2^k$的零花钱（秩落在$[k+1,\dots,2^k]$里）
总零花钱：对每个区间 $I_k$，秩 > $k$ 的节点数 ≤ $n/2^k$，因此该区间内所有节点获得的总钱数 ≤ n。
共有 $\log^ n$ 个区间，所以总零花钱 ≤ $n \log^* n$。

一次 find(x) 从 x 向上走到根，沿途节点 $v_0=x, v_1, \dots, v_t = \text{root}$。
将每一步 $(v_i \to v_{i+1})$ 分为两类：

• 跨区间：$\text{rank}(v_{i+1})$ 与 $\text{rank}(v_i)$ 属于不同区间（且更高）。

这样的步数最多等于区间个数，即 $O(\log^* n)$。

• 同区间：$\text{rank}(v_{i+1})$ 与 $\text{rank}(v_i)$ 属于同一区间。

这种步的代价由节点 $v_i$ 用自己的零花钱支付（1 元/步）。

设节点 v 的秩落在区间 $I_k = \{k+1,\dots,2^k\}$，它获得 $2^k$ 元。
每次 v 支付一元时，它的父节点秩严格增加（因为路径压缩会将 v 指向一个更高秩的节点，或最终指向根）。
由于父节点秩 ≤ $2^k$，且每次至少 +1，故 v 最多支付 $2^k$ 次就会使父节点秩超出该区间。
此后 v 再也不会遇到同区间爬升。因此 v 的零花钱恰好够支付所有同区间步。

设共有 m次 find 操作。

• 所有跨区间步的总数 ≤ $m \cdot (\log^* n)$。
• 所有同区间步的总代价 ≤ 所有节点零花钱之和 ≤ $n \log^* n$。

因此总时间 $T(m,n) = O(m \log^ n + n \log^ n) = O((m+n)\log^ n)$。
平摊到每次 find 为 $O(\log^ n)$。

Set Cover：
找到最小的点集，使得整个图中的所有点要么在这个点集中，要么与这个点集中的点相连
一个贪心的想法：每次加入与最多的未覆盖的点相连的点。直到彻底覆盖。
但是这个并不总是成立的。给出一个最简单的反例：
1-2-3-4-5
我如果第一次挑到3，那么就需要挑3个点，而很明显挑2和4两个点就够了。贪心算法失效了。
但是贪心算法虽然失效了，但是贪心可以保证我们的答案离最优解差的并没有很远。

假设 B 包含 n 个元素，且最优覆盖由 k 个集合组成。那么贪心算法至多使用 $k \ln n$ 个集合。
证明：设 $n_t$ 为贪心算法经过 $t$ 次迭代后仍未覆盖的元素个数（因此 $n_0 = n$）。由于剩余元素可以被最优的 $k$ 个集合覆盖，必然存在某个集合至少包含其中的 $n_t / k$ 个元素。因此，贪心策略将保证

重复应用该不等式可得

Chapter 6. Dynamic programming

前文已经讲到了DAG中的最短路就有dp的思想。
dp的最朴素思想就是解决某些子问题，然后我们可以通过子问题快速得到目前的答案。

Longest increasing subsequences：
先有一个转化：
我们对整个序列建图：如果 $a_{i} < a_{j}$ 且 $i < j$，则在i,j建一条权为1的边。
最后在这个DAG里找最长路就行。
$L_{j}=1+max\{L_{i},(i,j) \in E\}$
从这里来看，dp本质就是从某个子问题转移到另一个子问题，比如在这里，我们就解决了以 $a_{i}$ 结尾的最长上升子序列，于是我们就可以从这个子问题转移到以 $a_{j}$ 结尾的最长上升子序列中。
给出伪代码：

Edit distance：
比如我想在输入法里输入你好，即打入“nihao”，但是一手滑输入成了“nihoa”。现在大部分智能的输入法都能自动识别出你想要的是“nihao”。识别的重要依据就是两个字符串间的 edit distance，即把一个字符串修改为另一个字符串的最少修改次数。一个例子是：
从 sanow ->snowy，如果我们逐字替换，要用4次，但是很明显我们可以对比:
sanow_
s_nowy
这样改两次就行了。
可以抽象成以下两个集合间的距离：

定义E(i, j)为 $x[1,\dots,i]$ 和 $y[1,\dots,j]$ 的最少修改次数。
那么我们得到状态转移方程：

其中

翻译一下：1+E(i-1,j)就是把 $x_{i}$ 删了，1+E(i,j-1)就是把 $y_{j}$ 插进来，剩下那个就是如果相同就不动，不同就把 $x_{i}$ 改成 $y_{j}$ 。最后E(m,n)就是我们要的答案。
给出伪代码：

Knapsack：
背包问题的背景不再赘述。dp能做到 $O(n \cdot W)$。
值得注意的是，如果输入不是W量级而是$\log W$量级的话（也可以理解为W太大了），普通dp就不能做到多项式时间了。
对每个$w < W$，我们定义 $K(w)$ 为最多装w的情况下获得的最大价值。
那么现在对于无限背包问题（每个物品没有数量限制），有状态转移方程：