#创作计划# 图和数的爱情故事
2025-12-28 22:05:36
发布于：云南
图论和数论是 OI 圈的两大势力，但是好像并没有什么联姻。那么今天我这个媒婆就要把他们连在一起。
0. 前置知识
图论（Graph theory）：最短路、生成树、拓扑排序、Tarjan 等基本算法。
数论（Number theory）：公约数、不等式、同余等基本数论知识。
1. 差分约束
思考这么一个问题：
给出一组包含 个不等式，有 个未知数的形如：
的不等式组，求任意一组满足这个不等式组的解。
看到这个问题，相信大部分同学都会从数论这方面入手，但可能想了好久也没有一个解法。
但是转念一想： 的关系感觉像是一条路径的起点、终点和路径长度。
恭喜你，你发明了差分约束系统！
差分约束系统在 OI wiki 中的解释：
差分约束系统是一种特殊的 元一次不等式组，它包含 个变量 以及 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如：
其中 并且 是常数（可以是非负数，也可以是负数）。我们要解决的问题是：求一组解 ，使得所有的约束条件得到满足，否则判断出无解。
差分约束系统中的每个约束条件 都可以变形成 ，这与单源最短路中的三角形不等式 非常相似。
因此，我们可以把每个变量 看做图中的一个结点，对于每个约束条件 ，从结点 向结点 连一条长度为 的有向边。
注意到，如果 是该差分约束系统的一组解，那么对于任意的常数 ， 显然也是该差分约束系统的一组解，因为这样做差后 刚好被消掉。
那么接下来考虑怎么把不等式组的解和图论算法联系起来。我们目前已经建好图了，结合上面的解释，可以设 并向每一个点连一条权重为 边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则， 为该差分约束系统的一组解。
但是边存在负权，所以关于 Dijkstra 它死了，我们要用 SPFA。
那么模板题代码也就自然地出来了：
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;
}
除此之外，还有这些很经典的题，这里提供思路：
注意到存在区间关系，所以差分约束条件就很容易确定了：。但由于是大于等于，所以把模板题的最短路改成最长路即可。
这里只讲关于差分约束的转换：发现具有“至少”“至多”等字眼，因此我们根据题意列出不等式组：
特别地，最后一个式子转换成 也是正确的，所以要建双向边。那么这就是一个差分约束的板子了。
2. 同余最短路
这个东西非常抽象，主要可以解决以下几类问题：
- 给定 个整数，求这 个整数能拼凑出多少的其他整数（ 个整数可以重复取）。
- 给定 个整数，求这 个整数不能拼凑出的最小（最大）的整数。
- 至少要拼几次才能拼出模 余 的数。
那么根据上面所说的差分约束，我们可以把同余产生的状态视作最短路中的点，状态转移通常是这样的：。
但这还是太抽象了，我们先来看几道题：
居然是国家集训队的题！看来得好好讲讲了。
这类题容易想到转换为背包 dp 求解，但是 TLE。
我们可以分别求出 中符合条件的 的数量和 中符合条件的 的数量，前者减去后者即是答案。现在假设 是 中的一个数，那么对于 ，必定满足 。在这个式子中，显然 越小，符合条件的数就会越多。
考虑变成图论问题：我们可以用 表示 时的最小值。接下来连有向边 ，其中 ，边权为 ，表示从 变为 所花费的代价是 。 到 的最短路即是 时的最小值。
假定现在要求 中符合条件的 的数量，若这个最小值 ，则所有的 都符合条件，一共有 个。
所以枚举 ，累加就能得到答案。同时 取所有 的最小值最优，因为这样边数最少。
恭喜你，发明了同余最短路！
3. 图论转数论
上面讲了许多数论问题转为图论问题的解法，这里讲一讲图论问题如何转为数论。由于这类题没有一个固定的解法，所以直接从题入手。
首先点权相同的点可以缩在一起，这样剩下的点点权都是互不相同的。因为当 时 ，显然此时 应该是 的祖先。所以我们先检查是否连通，并考虑按点权从大到小枚举 ，对于所有点权为其倍数的还未设置父亲的点 ，将 的父亲设置为 ，全部设置完后再次枚举倍数检查是否成祖先关系。
对于 未出现的情况，我们可以枚举 的值，然后将点权为其倍数的点全部标记出来。可以发现如果所有被标记出来的点如果正好构成原树的一棵子树，那么这个 的值是不会出现的。如果为多棵，那么无解。
代码显然。
这里留下一道题给学有余力的读者思考：
启发下：首先，可以删掉图中无法从顶点 出发到达的点，和无法到达顶点 的点，因为无论怎么走都不可能经过这些点。那么删掉后的图是强联通的。
设 表示图中所有经过 的环长集合， 为 中所有数的 。那么若从 出发能恰好走 步回到 当且仅当 是 的约数。
那么我们现在就可以有一个清晰的思路：暴力把所有的环长求出来，取它们的 ，判断其是否为 的约数。
但是当经过 的环很多时，这种方法复杂度显然接受不了，所以考虑优化。
那么问题就变成了：给定若干个经过 的环，如何求出这些环长的 ？
恭喜你，成功完成了从图论到数论的转化。
接下来自己想吧，溜了溜了（
4. 应试技巧
当你打比赛的时候发现数之间的关系可以形成一个图的话，不妨想一想怎么把数论问题转化为图论问题，然后用图论经典模型去解决它。同理，遇到图论问题也可以想想怎么把它转为数论。
有些数论题目有很类似于图论的关系，比如差分约束系统中的差分关系 很容易看出对应了一条边上的 。或者是图论题目中出现许多数论标志，这里不展开去说。
但大多数题目没有很明显的转换标志，因此我们还需多加练习才能熟练掌握。
总之，一切技巧的目的都是把复杂问题简单化，所以我们可以从多方面思考一个问题，从而找到最简单的做法。
本笔记部分内容引自 OI Wiki 及百度百科。
如有不懂的问题欢迎随时提问！
有帮助，赞一个