图论和数论是 OI 圈的两大势力，但是好像并没有什么联姻。那么今天我这个媒婆就要把他们连在一起。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
0. 前置知识
图论（Graph theory）：最短路、生成树、拓扑排序、Tarjan 等基本算法。
数论（Number theory）：公约数、不等式、同余等基本数论知识。
1. 差分约束
思考这么一个问题：
给出一组包含 mmm 个不等式，有 nnn 个未知数的形如：
{xc1−xc1′≤y1xc2−xc2′≤y2⋯xcm−xcm′≤ym\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} ⎩⎨⎧ xc1 −xc1′ ≤y1 xc2 −xc2′ ≤y2 ⋯xcm −xcm′ ≤ym
的不等式组，求任意一组满足这个不等式组的解。
看到这个问题，相信大部分同学都会从数论这方面入手，但可能想了好久也没有一个解法。
但是转念一想：ci,ci′,yic_i,c'_i,y_ici ,ci′ ,yi 的关系感觉像是一条路径的起点、终点和路径长度。
恭喜你，你发明了差分约束系统！
差分约束系统在 OI wiki 中的解释：
> 差分约束系统是一种特殊的 nnn 元一次不等式组，它包含 nnn 个变量 x1,x2,⋯ ,xnx_1,x_2,\cdots,x_nx1 ,x2 ,⋯,xn 以及 mmm 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如：
>
> xi−xj≤ckx_i - x_j \leq c_k xi −xj ≤ck
>
> 其中 1≤i,j≤n,i≠j,1≤k≤m1 \leq i,j \leq n,i \not= j,1 \leq k \leq m1≤i,j≤n,i=j,1≤k≤m 并且 ckc_kck 是常数（可以是非负数，也可以是负数）。我们要解决的问题是：求一组解 x1=a1,x2=a2,⋯ ,xn=anx_1 = a_1,x_2 = a_2,\cdots,x_n = a_nx1 =a1 ,x2 =a2 ,⋯,xn =an ，使得所有的约束条件得到满足，否则判断出无解。
>
> 差分约束系统中的每个约束条件 xi−xj≤ckx_i - x_j \leq c_kxi −xj ≤ck 都可以变形成 xi≤xj+ckx_i \leq x_j + c_kxi ≤xj +ck ，这与单源最短路中的三角形不等式 dist[y]≤dist[x]+zdist[y] \leq dist[x] + zdist[y]≤dist[x]+z 非常相似。
>
> 因此，我们可以把每个变量 xix_ixi 看做图中的一个结点，对于每个约束条件 xi−xj≤ckx_i - x_j \leq c_kxi −xj ≤ck ，从结点 jjj 向结点 iii 连一条长度为 ckc_kck 的有向边。
>
> 注意到，如果 {a1,a2,…,an}\{a_1,a_2,\dots,a_n\}{a1 ,a2 ,…,an } 是该差分约束系统的一组解，那么对于任意的常数 ddd，{a1+d,a2+d,…,an+d}\{a_1 + d,a_2 + d,\dots,a_n + d\}{a1 +d,a2 +d,…,an +d} 显然也是该差分约束系统的一组解，因为这样做差后 ddd 刚好被消掉。
那么接下来考虑怎么把不等式组的解和图论算法联系起来。我们目前已经建好图了，结合上面的解释，可以设 dist[0]=0dist[0]=0dist[0]=0 并向每一个点连一条权重为 000 边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则，xi=dist[i]x_i=dist[i]xi =dist[i] 为该差分约束系统的一组解。
但是边存在负权，所以关于 Dijkstra 它死了，我们要用 SPFA。
那么模板题代码也就自然地出来了：
洛谷 P5960：差分约束
除此之外，还有这些很经典的题，这里提供思路：
SP 116：INTERVAL
注意到存在区间关系，所以差分约束条件就很容易确定了：xbi−xai−1≥cix_{b_i} - x_{a_i - 1} \geq c_ixbi −xai −1 ≥ci 。但由于是大于等于，所以把模板题的最短路改成最长路即可。
洛谷 P1993：小 K 的农场
这里只讲关于差分约束的转换：发现具有“至少”“至多”等字眼，因此我们根据题意列出不等式组：
{ai−aj≥cai−aj≤cai−aj=0\begin{cases} a_i-a_j \geq c \\a_i-a_j \leq c \\ a_i-a_j=0\end{cases} ⎩⎨⎧ ai −aj ≥cai −aj ≤cai −aj =0
特别地，最后一个式子转换成 aj−ai=0a_j-a_i=0aj −ai =0 也是正确的，所以要建双向边。那么这就是一个差分约束的板子了。
2. 同余最短路
这个东西非常抽象，主要可以解决以下几类问题：
* 给定 nnn 个整数，求这 nnn 个整数能拼凑出多少的其他整数（nnn 个整数可以重复取）。
* 给定 nnn 个整数，求这 nnn 个整数不能拼凑出的最小（最大）的整数。
* 至少要拼几次才能拼出模 kkk 余 ppp 的数。
那么根据上面所说的差分约束，我们可以把同余产生的状态视作最短路中的点，状态转移通常是这样的：f(i+w)=f(i)+wf(i+w)=f(i)+wf(i+w)=f(i)+w。
但这还是太抽象了，我们先来看几道题：
洛谷 P2371：墨墨的等式
居然是国家集训队的题！看来得好好讲讲了。
这类题容易想到转换为背包 dp 求解，但是 TLE。
我们可以分别求出 0∼r0 \sim r0∼r 中符合条件的 BBB 的数量和 0∼l−10 \sim l-10∼l−1 中符合条件的 BBB 的数量，前者减去后者即是答案。现在假设 mnmnmn 是 aia_iai 中的一个数，那么对于 a1x1+a2x2+⋯+anxn=ia_1x_1 + a_2x_2 + \dots + a_nx_n = ia1 x1 +a2 x2 +⋯+an xn =i，必定满足 a1x1+a2x2+⋯+anxn=i+k×mn (k∈N)a_1x_1 + a_2x_2 + \dots + a_nx_n = i + k \times mn \ (k \in
\mathbb{N})a1 x1 +a2 x2 +⋯+an xn =i+k×mn (k∈N)。在这个式子中，显然 iii 越小，符合条件的数就会越多。
考虑变成图论问题：我们可以用 dist[i]dist[i]dist[i] 表示 B mod mn=iB \bmod mn = iBmodmn=i 时的最小值。接下来连有向边 i→(i+aj)mod mni \to (i + a_j) \mod mni→(i+aj )modmn，其中 0≤i<mn0 \leq i < mn0≤i<mn，边权为 aja_jaj ，表示从 iii 变为 i+aji + a_ji+aj 所花费的代价是 aja_jaj 。000 到 iii 的最短路即是 B mod mn=iB \bmod mn = iBmodmn=i 时的最小值。
假定现在要求 0∼x0 \sim x0∼x 中符合条件的 BBB 的数量，若这个最小值 ≤x\leq x≤x，则所有的 i+k×mn (i+k×mn≤x,k∈N)i + k \times mn \ (i + k \times mn \leq x, k \in \mathbb{N})i+k×mn (i+k×mn≤x,k∈N) 都符合条件，一共有 ⌊x−dist[i]mn⌋+1\left\lfloor \frac{x - dist[i]}{mn} \right\rfloor + 1⌊mnx−dist[i] ⌋+1 个。
所以枚举 iii，累加就能得到答案。同时 mnmnmn 取所有 aia_iai 的最小值最优，因为这样边数最少。
恭喜你，发明了同余最短路！
3. 图论转数论
上面讲了许多数论问题转为图论问题的解法，这里讲一讲图论问题如何转为数论。由于这类题没有一个固定的解法，所以直接从题入手。
洛谷 P7854：GCD Tree
首先点权相同的点可以缩在一起，这样剩下的点点权都是互不相同的。因为当 ai∣aja_i | a_jai ∣aj 时 gcd(ai,aj)=ai\gcd(a_i,a_j)=a_igcd(ai ,aj )=ai ，显然此时 iii 应该是 jjj 的祖先。所以我们先检查是否连通，并考虑按点权从大到小枚举 iii，对于所有点权为其倍数的还未设置父亲的点 jjj，将 jjj 的父亲设置为 iii，全部设置完后再次枚举倍数检查是否成祖先关系。
对于 gcd\gcdgcd 未出现的情况，我们可以枚举 gcd\gcdgcd 的值，然后将点权为其倍数的点全部标记出来。可以发现如果所有被标记出来的点如果正好构成原树的一棵子树，那么这个 gcd\gcdgcd 的值是不会出现的。如果为多棵，那么无解。
代码显然。
这里留下一道题给学有余力的读者思考：
Atcoder abc306G：Return to 1
启发下：首先，可以删掉图中无法从顶点 111 出发到达的点，和无法到达顶点 111 的点，因为无论怎么走都不可能经过这些点。那么删掉后的图是强联通的。
设 LLL 表示图中所有经过 111 的环长集合，ddd 为 LLL 中所有数的 gcd\gcdgcd。那么若从 111 出发能恰好走 101010010^{10^{100}}1010100 步回到 111 当且仅当 ddd 是 101010010^{10^{100}}1010100 的约数。
那么我们现在就可以有一个清晰的思路：暴力把所有的环长求出来，取它们的 gcd\gcdgcd，判断其是否为101010010^{10^{100}}1010100 的约数。
但是当经过 111 的环很多时，这种方法复杂度显然接受不了，所以考虑优化。
那么问题就变成了：给定若干个经过 111 的环，如何求出这些环长的 gcd\gcdgcd？
恭喜你，成功完成了从图论到数论的转化。
接下来自己想吧，溜了溜了（
4. 应试技巧
当你打比赛的时候发现数之间的关系可以形成一个图的话，不妨想一想怎么把数论问题转化为图论问题，然后用图论经典模型去解决它。同理，遇到图论问题也可以想想怎么把它转为数论。
有些数论题目有很类似于图论的关系，比如差分约束系统中的差分关系 a,b,ca,b,ca,b,c 很容易看出对应了一条边上的 u,v,wu,v,wu,v,w。或者是图论题目中出现许多数论标志，这里不展开去说。
但大多数题目没有很明显的转换标志，因此我们还需多加练习才能熟练掌握。
总之，一切技巧的目的都是把复杂问题简单化，所以我们可以从多方面思考一个问题，从而找到最简单的做法。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
本笔记部分内容引自 OI Wiki 及百度百科。
如有不懂的问题欢迎随时提问！
