浅谈数论意义下的图论

· · 算法·理论

图论和数论是 OI 圈的两大势力，但是好像并没有什么联姻。那么今天我这个媒婆就要把他们连在一起。

0. 前置知识

图论（Graph theory）：最短路、生成树、拓扑排序、Tarjan 等基本算法。

数论（Number theory）：公约数、不等式、同余等基本数论知识。

1. 差分约束

思考这么一个问题：

给出一组包含 m 个不等式，有 n 个未知数的形如：

\begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases}

的不等式组，求任意一组满足这个不等式组的解。

看到这个问题，相信大部分同学都会从数论这方面入手，但可能想了好久也没有一个解法。

但是转念一想：c_i,c'_i,y_i 的关系感觉像是一条路径的起点、终点和路径长度。

恭喜你，你发明了差分约束系统！

:::info[差分约束系统在 OI wiki 中的解释] 差分约束系统是一种特殊的 n 元一次不等式组，它包含 n 个变量 x_1,x_2,\cdots,x_n 以及 m 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如：

x_i - x_j \leq c_k

其中 1 \leq i,j \leq n,i \not= j,1 \leq k \leq m 并且 c_k 是常数（可以是非负数，也可以是负数）。我们要解决的问题是：求一组解 x_1 = a_1,x_2 = a_2,\cdots,x_n = a_n，使得所有的约束条件得到满足，否则判断出无解。

差分约束系统中的每个约束条件 x_i - x_j \leq c_k 都可以变形成 x_i \leq x_j + c_k，这与单源最短路中的三角形不等式 dist[y] \leq dist[x] + z 非常相似。

因此，我们可以把每个变量 x_i 看做图中的一个结点，对于每个约束条件 x_i - x_j \leq c_k，从结点 j 向结点 i 连一条长度为 c_k 的有向边。

注意到，如果 \{a_1,a_2,\dots,a_n\} 是该差分约束系统的一组解，那么对于任意的常数 d，\{a_1 + d,a_2 + d,\dots,a_n + d\} 显然也是该差分约束系统的一组解，因为这样做差后 d 刚好被消掉。 :::

那么接下来考虑怎么把不等式组的解和图论算法联系起来。我们目前已经建好图了，结合上面的解释，可以设 dist[0]=0 并向每一个点连一条权重为 0 边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则，x_i=dist[i] 为该差分约束系统的一组解。

但是边存在负权，所以关于 Dijkstra 它死了，我们要用 SPFA。

那么模板题代码也就自然地出来了：

洛谷 P5960：差分约束

bool spfa(int s){
    // 自己写板子
}
signed main(){
    // 从 0 连边
    // m 个差分约束建图
    if(!spfa(0)) cout << "NO";
    else{
        for(int i = 1;i <= n;i++) cout << d[i] << " ";
    }
    return 0;
}

除此之外，还有这些很经典的题，这里提供思路：

SP 116：INTERVAL

注意到存在区间关系，所以差分约束条件就很容易确定了：x_{b_i} - x_{a_i - 1} \geq c_i。但由于是大于等于，所以把模板题的最短路改成最长路即可。

洛谷 P1993：小 K 的农场

这里只讲关于差分约束的转换：发现具有“至少”“至多”等字眼，因此我们根据题意列出不等式组：

\begin{cases} a_i-a_j \geq c \\a_i-a_j \leq c \\ a_i-a_j=0\end{cases}

特别地，最后一个式子转换成 a_j-a_i=0 也是正确的，所以要建双向边。那么这就是一个差分约束的板子了。

2. 同余最短路

这个东西非常抽象，主要可以解决以下几类问题：

那么根据上面所说的差分约束，我们可以把同余产生的状态视作最短路中的点，状态转移通常是这样的：f(i+w)=f(i)+w。

但这还是太抽象了，我们先来看几道题：

洛谷 P2371：墨墨的等式

居然是国家集训队的题！看来得好好讲讲了。

这类题容易想到转换为背包 dp 求解，但是 TLE。

我们可以分别求出 0 \sim r 中符合条件的 B 的数量和 0 \sim l-1 中符合条件的 B 的数量，前者减去后者即是答案。现在假设 mn 是 a_i 中的一个数，那么对于 a_1x_1 + a_2x_2 + \dots + a_nx_n = i，必定满足 a_1x_1 + a_2x_2 + \dots + a_nx_n = i + k \times mn \ (k \in \mathbb{N})。在这个式子中，显然 i 越小，符合条件的数就会越多。

考虑变成图论问题：我们可以用 dist[i] 表示 B \bmod mn = i 时的最小值。接下来连有向边 i \to (i + a_j) \mod mn，其中 0 \leq i < mn，边权为 a_j，表示从 i 变为 i + a_j 所花费的代价是 a_j。0 到 i 的最短路即是 B \bmod mn = i 时的最小值。

假定现在要求 0 \sim x 中符合条件的 B 的数量，若这个最小值 \leq x，则所有的 i + k \times mn \ (i + k \times mn \leq x, k \in \mathbb{N}) 都符合条件，一共有 \left\lfloor \frac{x - dist[i]}{mn} \right\rfloor + 1 个。

所以枚举 i，累加就能得到答案。同时 mn 取所有 a_i 的最小值最优，因为这样边数最少。

恭喜你，发明了同余最短路！

3. 图论转数论

上面讲了许多数论问题转为图论问题的解法，这里讲一讲图论问题如何转为数论。由于这类题没有一个固定的解法，所以直接从题入手。

洛谷 P7854：GCD Tree

首先点权相同的点可以缩在一起，这样剩下的点点权都是互不相同的。因为当 a_i | a_j 时 \gcd(a_i,a_j)=a_i，显然此时 i 应该是 j 的祖先。所以我们先检查是否连通，并考虑按点权从大到小枚举 i，对于所有点权为其倍数的还未设置父亲的点 j，将 j 的父亲设置为 i，全部设置完后再次枚举倍数检查是否成祖先关系。

对于 \gcd 未出现的情况，我们可以枚举 \gcd 的值，然后将点权为其倍数的点全部标记出来。可以发现如果所有被标记出来的点如果正好构成原树的一棵子树，那么这个 \gcd 的值是不会出现的。如果为多棵，那么无解。

代码显然。

这里留下一道题给学有余力的读者思考：

Atcoder abc306G：Return to 1

启发下：首先，可以删掉图中无法从顶点 1 出发到达的点，和无法到达顶点 1 的点，因为无论怎么走都不可能经过这些点。那么删掉后的图是强联通的。

设 L 表示图中所有经过 1 的环长集合，d 为 L 中所有数的 \gcd。那么若从 1 出发能恰好走 10^{10^{100}} 步回到 1 当且仅当 d 是 10^{10^{100}} 的约数。

那么我们现在就可以有一个清晰的思路：暴力把所有的环长求出来，取它们的 \gcd，判断其是否为10^{10^{100}} 的约数。

但是当经过 1 的环很多时，这种方法复杂度显然接受不了，所以考虑优化。

那么问题就变成了：给定若干个经过 1 的环，如何求出这些环长的 \gcd？

恭喜你，成功完成了从图论到数论的转化。

接下来自己想吧，溜了溜了（

4. 应试技巧

当你打比赛的时候发现数之间的关系可以形成一个图的话，不妨想一想怎么把数论问题转化为图论问题，然后用图论经典模型去解决它。同理，遇到图论问题也可以想想怎么把它转为数论。

有些数论题目有很类似于图论的关系，比如差分约束系统中的差分关系 a,b,c 很容易看出对应了一条边上的 u,v,w。或者是图论题目中出现许多数论标志，这里不展开去说。

但大多数题目没有很明显的转换标志，因此我们还需多加练习才能熟练掌握。

总之，一切技巧的目的都是把复杂问题简单化，所以我们可以从多方面思考一个问题，从而找到最简单的做法。

本笔记部分内容引自 OI Wiki 及百度百科。

如有不懂的问题欢迎随时提问！