对于数论函数 $f$ 定义前缀和 $S_f(n)=\sum_{i=1}^nf(i)$。

如果有两个数论函数 $f,g$ 满足我们可以快速计算 $S_g$ 和 $S_{f*g}$，可以通过杜教筛快速求出 $S_f(n)$。

$$\displaylines{\begin{aligned} S_{f*g}(n)=&\sum_{i=1}^n\sum_{d|i}g(d)f\left(\frac id\right)\\ =&\sum_{d=1}^ng(d)\sum_{k=1}^{\lfloor\frac nd\rfloor}f(k)\\ =&\sum_{d=1}^ng(d)S_f(\left\lfloor\frac nd\right\rfloor) \end{aligned} }$$

于是有

$$\displaylines{g(1)S_f(n)=S_{f*g}(n)-\sum_{d=2}^ng(d)S_f(\left\lfloor\frac nd\right\rfloor) }$$

直接利用该式记忆化地递归求解，因为

$$\displaylines{\left\lfloor\frac{\lfloor\frac n{d_1}\rfloor}{d_2}\right\rfloor=\left\lfloor\frac n{d_1d_2}\right\rfloor }$$

所以我们只在所有 $\lfloor\frac nd\rfloor$ 处求了 $S_f$ 的值（其中 $d$ 是 $[1,n]$ 内的整数），每次求值使用整除分块，将 $d$ 以 $\sqrt n$ 为界分开考虑，总复杂度如下：

$$\displaylines{\begin{aligned} &O\left(\sum_{i=1}^{\sqrt n}\sqrt i+\sum_{i=1}^{\sqrt n}\sqrt\frac ni\right)\\ =&O\left(\int_0^{\sqrt n}\sqrt x\mathrm dx+\int_0^{\sqrt n}\sqrt\frac nx\mathrm dx\right)\\ =&O\left(\left.x^{\frac32}\right|_0^{\sqrt n}+\left.\sqrt{nx}\right|_0^{\sqrt n}\right)\\ =&O\left(n^\frac34\right) \end{aligned} }$$

如果 $f$ 可以通过线性筛预处理出不超过 $K$ 的 $S_f$ 值，复杂度可以进一步优化。因为只求所有不超过 $\sqrt n$ 处的 $S_f$ 值已经达到了 $O(n^\frac34)$ 的复杂度，所以想要优化复杂度，$K$ 至少为 $\sqrt n$。所以有

$$\displaylines{\begin{aligned} &O\left(K+\sum_{i=1}^\frac nK\sqrt\frac ni\right)\\ =&O\left(K+\left.\sqrt{nx}\right|_0^{\frac nK}\right)\\ =&O\left(K+nK^{-\frac12}\right) \end{aligned} }$$

$K=O(n^\frac 23)$ 时复杂度平衡，为 $O(n^\frac 23)$。

素性测试

二次探测定理：对于质数 $p$，方程 $x^2\equiv1\pmod p$ 的解只有 $x\equiv\pm1\pmod p$。

证明：$(x+1)(x-1)\equiv x^2-1\equiv1\pmod p$，于是 $p\mid(x+1)(x-1)$。由于 $p$ 是质数，$p\mid x+1$ 或 $p\mid x-1$ 至少有一个成立。$\square$

这意味着，如果我们想判定 $p$ 的素性，我们可以尝试找出 $x\not\equiv\pm1\pmod p$ 而 $x^2\equiv1\pmod p$ 的 $x$。一旦我们找出了一个这样的 $x$，$p$ 一定不是素数。而在经过大量检测后没有找到这样的 $x$，我们即宣称 $p$ 是素数（并且我们确实能够证明这样做的正确性）。

考察费马小定理 $a^{p-1}\equiv1\pmod p$，其中 $p$ 为素数。我们将 $p-1$ 表示为 $2^sd$，其中 $d$ 为奇数。

如果我们任选一个 $(0,p)$ 内的整数作为底数 $a$，将 $d,2d,4d,\cdots,2^{s-1}d$ 分别代入 $x$，如果有 $a^{2^kd}\not\equiv\pm1\pmod p$ 而 $a^{2^{k+1}d}\equiv1\pmod p$ 则说明 $p$ 不是质数。如果 $a^{p-1}\not\equiv1\pmod p$ 也说明 $p$ 不是质数。

可以证明，能够将一个非质数 $n$ 判别出来的底数 $a$ 至少有 $\left\lfloor\frac{n-1}2\right\rfloor$ 个。也即在 $(0,n)$ 中随机选取 $a$，将非质数判别为质数的概率不超过 $\frac12$，那么随机选择多个底数分别判断即可达到较高正确率。

如果广义黎曼猜想成立，只需以 $[2,\min\{n-2,\lfloor2\ln^2n\rfloor\}]$ 的所有数分别作为底数 $a$ 进行探测，即可确定 $n$ 的素性而不依赖于概率分析。而对于 OI 中常见的 $[1,2^{64})$ 中的所有数，只用不超过 $40$ 的 $12$ 个质数即可。

分解质因数

对于合数 $n$，通过枚举获取 $n$ 的因数是困难的，可以考虑以一定的方式生成一些 $k$，通过求 $\gcd(n,k)$ 获取 $n$ 的非平凡因子。那么我们要做的就是尽量减小 $\gcd(n,k)$ 为 $1$ 或 $n$ 的概率。

考虑数列 $a_0=0,a_i=(a_{i-1}^2+c)\bmod n$，其中 $c$ 是 $(1,n)$ 内的任意整数。设 $n$ 有某一因子 $k$。显然数列 $\{a_i\bmod k\}$ 一定会在有限项内进入循环。而 $a_i\bmod k=a_j\bmod k$ 意味着 $k\mid a_i-a_j$，此时如果 $n\nmid a_i-a_j$ 的话，$\gcd(n,a_i-a_j)$ 即为 $n$ 的一个非平凡因子，否则分解失败。

具体实现有两种。

第一种实现本质上是 Floyd 判环算法，从小到大枚举 $i$，如果某次 $k=\gcd(a_i-a_{2i},n)$ 不为 $1$，说明数列 $\{a_n\bmod k\}$ 在第 $i$ 项之前已进入循环。

第二种实现是利用倍增，将两个指针 $s,t$ 初始设为 $0$，第 $i$ 轮 $t$ 向后移动 $2^{i-1}$ 步，每步之后检查 $\gcd(n,s-t)$，该轮结束后将 $s$ 赋为 $t$。为了进一步优化常数，每 $127$ 步检验近 $127$ 步中 $s-t$ 的累乘结果。实验表明，$127$ 是一个很好的参数，过小会导致求 $\gcd$ 的次数较多，过大会导致累乘结果得到 $0$ 的概率过大，频繁失败。

两种实现的期望复杂度均为 $O(m\log a)$。其中 $m$ 为 $\min_{d|n}\#\{a_i\bmod d\mid i\in\mathbb N\}$ 在 $c$ 均匀随机时的期望。首先该值一定小于 $\#\{a_i\bmod k\mid i\in\mathbb N\}$，其中 $k$ 为 $n$ 的最小质因子。

那么期望多少项 $\{a_i\bmod k\}$ 会开始循环呢？首先我们发现该数列在 $(1,k)$ 内的分布较为均匀（这也是选择 $(x^2+c)\bmod n$ 来生成数列下一项的原因），所以该数列进入循环的项数等同于不断在 $k-1$ 个元素中均匀随机选取，第一次取到已经出现过的数的期望次数。

在 $n$ 个元素中进行 $t$ 次选择结果两两不同的概率为 $P=\prod_{i=0}^{t-1}\frac{n-i}n$，由 $1+x\le e^x$ 有

$$\displaylines{P=\prod_{i=0}^{t-1}\frac{n-i}n\le\prod_{i=0}^{t-1}\exp\left(-\frac in\right)=\exp\left(-\frac{t(t-1)}{2n}\right) }$$

于是对于 $p\in(0,1)$，

$$\displaylines{P\le p\Longleftarrow\exp\left(-\frac{t(t-1)}{2n}\right)\le p\iff t(t-1)\ge-2n\ln p\Longleftarrow t\ge\sqrt{-2n\ln p} }$$

将 $t$ 次选取看作一次实验，根据独立随机试验的结论，这样的实验失败一次的期望次数为 $\frac1{1-p}$，故在 $k-1$ 个元素中随机选取，直到得到相同元素的期望次数不超过

$$\displaylines{\frac1{1-p}\sqrt{-2(k-1)\ln p}=O(\sqrt k) }$$

于是该算法的复杂度为 $O(m\log a)=O(\sqrt k\log a)=O(\sqrt[4]n\log a)$。

如果存在凸函数 $f(x)$，我们无从得知其在某个 $x$ 处的值，但是可以求出某个斜率的直线切它时切点的位置。注意到切点的横坐标关于直线斜率存在单调性，可以依此二分，找出任意一个与凸包切于该点的一次函数，即可计算出该函数在某个 $x$ 处的值。

Floyd 全源最短路

设 $f_{t,u,v}$ 为只经过图中 $[1,t]\cup\{u,v\}$ 中的点，$u\to v$ 的最短路。$f_{0,u,v}$ 即 $u$ 到 $v$ 的所有边中的边权最小值，$u$ 到 $v$ 间无边即为 $+\infty$。

那么转移为 $f_{t,u,v}\xleftarrow[k]{\min}f_{t-1,u,k}+f_{t-1,k,v}$。复杂度 $O(n^3)$

Bellman-Ford 单源最短路

维护 $d_u$，第 $t$ 轮更新时表示从起点到点 $u$ 经过不超过 $t$ 条路径的最短路。

每轮更新时遍历每条边 $(u,v,w)$，令 $d_v\xleftarrow[]{\min}d_u+w$。

这样做的正确性是显然的，考虑到若原图存在最短路，那么起点到每个点一定存在一条长度不超过 $n-1$ 的最短路。所以在经历 $n-1$ 轮更新后 $d_i$ 即为起点到 $i$ 的最短路；也即如果第 $n$ 轮更新仍然有 $d$ 变小，说明原图不存在最短路，即存在负环。

时间复杂度 $O(nm)$。

SPFA 单源最短路

Bellman-Ford 中每轮更新会遍历一遍所有点。实际上只有上一轮中 $d$ 减小的那些点有更新其它点的能力。所以我们维护一个队列，每次取队头出来更新其它点。

显然一个点 $u$ 第 $t$ 次入队时，$d_u$ 一定小于等于 Bellman-Ford 中第 $t$ 轮更新后 $d_u$ 的值。那么一个点入队 $n$ 次说明原图存在负环。

时间复杂度 $O(nm)$。

Dijkstra 单源最短路

对于一个无负权边的图，维护一个集合 $S$ 包含所有已经求得最短路的点。初始为空集。

再维护 $d_i$ 表示用 $S$ 中的点能够更新得的每个点最短路，特殊地，起点的 $d$ 值为 $0$。

每轮更新时，考察不在 $S$ 中的所有点中 $d$ 最小者 $i$，由于在 $S$ 中的点已经更新过了，不在 $S$ 中的点已经无法再更新它，所以此时 $d_i$ 即为 $i$ 的最短路。将其加入 $S$ 并更新其它所有点。

找出不在 $S$ 中的所有点中 $d$ 最小值这一步，暴力求得时间复杂度为 $O(n^2)$，使用不支持删除的堆（priority_queue）为 $O(m\log m)$，使用支持删除的堆为 $O(m\log n)$，使用支持 $O(1)$ 插入的堆（斐波那契堆、配对堆等）为 $O(n\log n+m)$。

Johnson 全源最短路

对于无负权边的图，全源最短路可以对每个点都做一遍 Dijkstra，时间复杂度为 $O(nF(n,m))$，其中 $F(n,m)$ 为一轮 Dijkstra 的时间复杂度，若使用堆实现，其时间复杂度低于 Floyd 的 $O(n^3)$。

对于一般图没办法直接应用 Dijkstra。我们尝试给每个点 $t$ 都规定一个权值 $h_t$，并将每条边 $(u,v,w)$ 边权改为 $w+h_u-h_v$。不难发现，无论 $h$ 取什么值，新图最短路即原图最短路，且新图上 $s\to t$ 的最短路长度为原图上 $s\to t$ 的最短路长度加上 $h_s-h_t$。

为了使新图能够应用 Dijkstra，我们需要求出一组合适的 $h$ 使新图上没有负权边。即对于每条边 $(u,v,w)$ 有 $w+h_u-h_v\ge0$。于是变成了一个差分约束问题。先做一遍 SPFA 得到 $h$，修改边权，然后以每个点为起点分别做一遍 Dijkstra，最后求得原图上最短路即可。

做法

核心在于维护失配指针，即每个节点指向 Trie 中存在的最长真后缀。

先建出 Trie 树。将根节点的后继节点加入作为起始节点 bfs。

bfs 的过程中，对于当前节点遍历字符集中的每个字符 $c$。

• 如果 $u$ 存在转移 $c$，那么这条转移的终点的失配指针应当指向 $u$ 的失配指针指向的节点向 $c$ 转移的结果，然后将这条转移的终点加入 bfs 队列。
• 如果 $u$ 不存在转移 $c$，那么新建一条向 $c$ 转移至 $u$ 的失配指针指向的节点向 $c$ 转移的结果。

不难发现从一个节点走向它失配指针指向的位置，它所代表的字符串的长度单调减少。因此从一个节点一直这样走，最后一定能够走到 Trie 的根节点。于是失配指针的关系构成了有根一棵树，以每个节点为根的子树即以这个节点为后缀的所有节点。

记号

• $\Sigma$ 表示字符集
• $\Sigma^\ast$ 表示这个字符集能构成的所有字符串
• $\lambda$ 表示空字符串
• $|w|$ 表示字符串 $w$ 的长度
• $w_i$ 表示字符串 $w$ 的第 $i$ 个字符。
• $xy$ 表示字符串 $x$ 与 $y$ 拼接得到的字符串

end-pos 函数

对于某个字符串 $w=a_1,\cdots,a_n\in\Sigma^\ast(a_1,\cdots,a_n\in\Sigma)$ 和 $t\in\Sigma^\ast$，$\operatorname{end-pos}_w(t)=\{i\mid t=a_{i-|y|+1}\cdots a_i\}$。特殊地，$\operatorname{end-pos}_w(\lambda)=\{0,1,2,\cdots,n\}$。不会混淆的情况下可以简记作 $\operatorname{end-pos}(t)$。

称字符串 $s$ 的两个子串 $x,y$ 右端点等价，当且仅当 $\operatorname{end-pos}_w(x)=\operatorname{end-pos}_w(y)$，记作 $x\overset w\equiv y$，简记作 $x\equiv y$。右端点等价显然是一种等价关系，于是我们可以将 $x$ 所在的等价类记作 $[x]_w$，简记作 $[x]$。

引理 1.1 显然：

1. 在字符串右侧追加字符能够保持右端点等价关系，即 $x\equiv y\Rightarrow xz\equiv yz$
2. 如果两个子串右端点等价，则其中一个为另一个的后缀
3. 两个字符串 $xy$ 与 $y$ 右端点等价，当且仅当 $y$ 每次出现，$x$ 都紧接着出现在其左侧
4. $x$ 是 $[x]$ 中最长的子串，当且仅当存在以下两种情况之一：$x$ 是 $s$ 的前缀；$x$ 在 $s$ 的两个位置出现时左侧紧邻不同的字符

如果 $x$ 为某个等价类中最长的子串，我们称 $x$ 代表该等价类。

有向无环字符串图（DAWG）

DAWG（Directed Acyclic Word Graph）$D_w$ 定义为满足以下条件的有限状态自动机：

• 字符集为 $\Sigma$
• 状态与 $s$ 中的右端点等价类一一对应
• 转移为 $[x]\overset a\to[xa]$，其中 $xa$ 为 $w$ 的子串（注意到右端点等价具有右复合不变性，这保证了某个状态对于某个字符的转移是唯一的）
• 起始状态为 $[\lambda]$
• 每一个状态都是接受状态

下文混用“状态”与“右端点等价类”两种说法。

引理 1.2 $D_w$ 能够识别 $w$ 的所有子串。

证明： 构成 $D_w$ 的接受状态的右端点等价类的并即该字符串的所有子串，由 Nerode 定理易证。$\Box$

DAWG 不一定是能够识别 $w$ 的所有子串的最小 DFA。

后缀自动机（SAM）的性质

SAM（Suffix Automaton）$S_w$ 定义为，在 $D_w$ 的基础上，将接受状态改为所有后缀所在的等价类，即 $\operatorname{end-pos}$ 值包括 $|w|$ 的所有等价类。

定理 1.3 对于任意 $w\in S^\ast$，$S_w$ 是最小的能够识别 $w$ 所有后缀的有限状态自动机

证明： 由定义，$S_w$ 所有接受状态的并集即 $w$ 的所有后缀，所以 $S_w$ 能够识别 $w$ 的所有后缀。欲证明最小性，不难发现对于任意 $x\equiv y$ 和 $z\in\Sigma^\ast$，$xz$ 是 $w$ 后缀当且仅当 $yz$ 是 $w$ 后缀，于是由 Nerode 定理易证。$\Box$

如果两个子串的 $\operatorname{end-pos}$ 集合有交，那么其中一个一定是另一个的子串，于是前者的 $\operatorname{end-pos}$ 值是后者的 $\operatorname{end-pos}$ 值的超集。所以某个字符串 $w$ 的所有等价类能够由此关系构造一棵有根树，使得 $\operatorname{end-pos}(u)$ 是 $\operatorname{end-pos}(v)$ 的超集当且仅当 $u$ 在树上为 $v$ 的祖先。下文把这棵树称作 parent 树 $T(w)$。

定理 1.4 如果 $x$ 在 $w$ 中代表某个等价类 $[x]$，那么 parent 树上该等价类的子节点为 $[ax]$，其中 $a\in\Sigma$，且 $ax$ 在 $w$ 中至少出现过一次。

证明 根据定义，$[x]$ 在 $T(w)$ 上子节点对应的 $\operatorname{end-pos}$ 为所有极大的合法的 $\operatorname{end-pos}(x)$ 的真子集，即一定能够表示为某个 $\operatorname{end-pos}(ax)$，其中 $a\in\Sigma$。$\Box$

由定理 1.4，$T(w)$ 为 $w$ 反串的后缀树。

引理 1.5 对于长度大于等于 $2$ 字符串 $w$，$S_w$ 最多有 $2|w|-1$ 个状态。

证明 特别地，对于 $w=a^n$（$n>2$），$S_w$ 有 $n+1$ 个状态。否则我们将 $T(w)$ 上的所有节点分类讨论。

如果某个子串 $x$ 在 $w$ 中两个位置出现时左侧紧邻不同字符，那么 $[x]$ 至少有两个子节点。因此根据引理 1.1 的 4，只有 $0$ 个或 $1$ 个子节点的等价类的代表元一定是 $w$ 的前缀。因为某个前缀只能出现在一个等价类中，并且由于 $w$ 由至少两种字符构成，$[\lambda]$ 至少有 $2$ 个子节点，所以有 $0$ 个或 $1$ 个子节点的等价类不多于非空前缀，所以最多有 $|w|$ 个。

而因为树的性质，至少有 $2$ 个子节点的节点个数少于总节点数的一半，所以总节点数少于有 $0$ 个或 $1$ 个子节点的节点个数的两倍，即最多有 $2|w|-1$ 个。$\Box$

$S_w$ 节点数达到此上界，当且仅当 $w=ab^n$，其中 $a\not=b$，在此不做证明。

引理 1.6 对于长度大于等于 $2$ 的字符串 $w$，$S_w$ 的转移边数最多比状态数多 $|w|-2$。

证明 对于 $S_w$ 的任一生成树，其树边比状态数少 $1$。而对于每一条非树边 $(p,q)$，都可以构造出至少一条从 $[\lambda]$ 到 $[w]$ 的路径，使得该非树边为路径中第一条非树边。具体构造方案为：在生成树上从 $[\lambda]$ 到 $p$，从 $p$ 到 $q$，因为 $S_w$ 上仅有 $[w]$ 一个点出度为零并且图上无环，所以至少存在一条从 $q$ 到 $[w]$ 的路径。因为 $w$ 有 $|w|-1$ 个后缀经过了至少一条非树边，每个后缀对应唯一一条从 $[\lambda]$ 到 $[w]$ 的路径，所以非树边最多有 $|w|-1$ 条。于是有 $S_w$ 的转移边数最多比状态数多 $|w|-2$。$\Box$

结合引理 1.5 和引理 1.6 有如下结论。

定理 1.7 对于长度大于 $2$ 的字符串 $w$，$S_w$ 的状态数最多为 $2|w|-1$，转移边数最多为 $3|w|-4$。

证明 由引理 1.6，转移边数不超过状态数加 $|w|-2$。因此转移边数一个较松的上界为 $3|w|-3$。转移边数达到这个上界，仅当状态数达到 $2|w|-1$ 的上界，即 $w$ 形如 $ab^n$，此时转移边数为 $2|w|-1$，无法达到该上界。因此转移边数的上界为 $3|w|-4$。

达到该上界当且仅当 $w=ab^nc$，其中 $a,b,c$ 两两不同。

构建 SAM 的在线算法

考虑对从短到长每个前缀依此建出其对应的 SAM。于是只需要考虑一个字符串末尾加入某个字符后 SAM 的变化即可。

教主的魔法（区间加 区间查排名）

分块并维护块内排序后的结果，设块长为 $B$。

区间加时，整块打 tag，散块暴力修改后排序。

区间查询 rank，整块二分，散块暴力统计。

这样时间复杂度为 $O(q\log(B)(\dfrac nB+B))$

---

考虑到区间加时，散块中被修改的和未被修改的部分内部，相对大小关系不变，可以 $O(B)$ 归并。

这样时间复杂度为为 $O(q\log(B)\dfrac nB+qB)$，$B$ 取 $\sqrt{n\log n}$ 以平衡复杂度。

由乃打扑克（区间加 区间查第 k）

类似地，分块维护块内排序内的结果，设块长为 $B$。

区间加时，整块打 tag，散块同样 $O(B)$ 归并。

区间查询第 k，通过二分答案转化为查询 rank。

这样时间复杂度为 $O(q\log(w)(\dfrac nB+B))$。

---

二分后，在散块中查询 rank 时可以将至多两个散块归并到一个新数组，从而将查询 rank 的 $O(B)$ 的时间复杂度变为 $O(\log B)$。

这样时间复杂度为 $O(q\log(w)(\dfrac nB\log B+\log B)+q(\dfrac nB+B))=O(q\log(w)\dfrac nB\log B+qB)$，一般近似地认为 $\log w$ 和 $\log B$ 同阶。取 $\sqrt{n}\log w$ 以平衡时间复杂度。

---

二分时可以使用分散层叠减少二分次数，达到 $O(q\sqrt n)$ 的时间复杂度。

见 gxy001 的博客。

问题形式

解 $n$ 元一次不等式组，每个不等式形如 $x_i-x_j\le k$。

• 求是否有解
• 给定解的上/下限，求最大/最小解

方法

用最短路的性质（$(u,v,w)\in G\Rightarrow \operatorname{dis}_v\le\operatorname{dis}_u+w$）保证解符合方程（最长路同理）。

1. 最大解问题转化为最短路，最小解问题转化为最长路。
2. 将不等式转化为最短路/最长路性质的形式，建边。
3. 建立源点，向每个节点连出一条长为上/下限的边。
4. 求单源最短路/最长路，结果就是不等式组的最大/最小解

如果只要求判定是否有解，3、4 步删去，用 SPFA 判定是否有负环/正环。

典例

[SCOI2011] 糖果

因为建完图之后任意边的边权非负，所以一个环内出现正权极为无解，强连通分量缩点后拓扑排序求最长路。