同余最短路
当出现形如「给定 𝑛n
个整数，求这 𝑛n 个整数能拼凑出多少的其他整数（𝑛n 个整数可以重复取）」，以及「给定 𝑛n 个整数，求这 𝑛n 个整数不能拼凑出的最小（最大）的整数」，或者「至少要拼几次才能拼出模 𝐾K 余 𝑝p 的数」的问题时可以使用同余最短路的方法．
同余最短路利用同余来构造一些状态，可以达到优化空间复杂度的目的．
类比 差分约束 方法，利用同余构造的这些状态可以看作单源最短路中的点．同余最短路的状态转移通常是这样的 𝑓(𝑖 +𝑦) =𝑓(𝑖) +𝑦f(i+y)=f(i)+y，类似单源最短路中 𝑓(𝑣) =𝑓(𝑢) +𝑒𝑑𝑔𝑒(𝑢,𝑣)f(v)=f(u)+edge(u,v)．
例题
例题一
题目大意：给定 𝑥，𝑦，𝑧，ℎx，y，z，h，对于 𝑘 ∈[1,ℎ]k∈[1,h]，有多少个 𝑘k 能够满足 𝑎𝑥 +𝑏𝑦 +𝑐𝑧 =𝑘ax+by+cz=k．（0 ≤𝑎,𝑏,𝑐0≤a,b,c，1 ≤𝑥,𝑦,𝑧 ≤1051≤x,y,z≤105，ℎ ≤263 −1h≤263−1）
不妨假设 𝑥 <𝑦 <𝑧x<y<z．
令 𝑑𝑖di 为只通过 操作 2 和 操作 3 ，需满足 𝑝mod𝑥 =𝑖pmodx=i 能够达到的最低楼层 𝑝p，即 操作 2 和 操作 3 操作后能得到的模 𝑥x 下与 𝑖i 同余的最小数，用来计算该同余类满足条件的数个数．
可以得到两个状态：
- 𝑖𝑦→(𝑖 +𝑦)mod𝑥i→y(i+y)modx
- 𝑖𝑧→(𝑖 +𝑧)mod𝑥i→z(i+z)modx
注意通常选取一组 𝑎𝑖ai 中最小的那个数对它取模，也就是此处的 𝑥x，这样可以尽量减小空间复杂度（剩余系最小）．
那么实际上相当于执行了最短路中的建边操作：
add(i, (i+y) % x, y)
add(i, (i+z) % x, z)
接下来只需要求出 𝑑0,𝑑1,𝑑2,…,𝑑𝑥−1d0,d1,d2,…,dx−1，只需要跑一次最短路就可求出相应的 𝑑𝑖di．
基于最短路的实现
---|---
但是事实上也不需要进行正常的最短路求解，注意到有两个特殊的性质：
首先，只有两种边权，且对于每一条路径，由于加法交换律，走两种边权的顺序是无影响的．因此可以考虑做两次最短路，每次只建出一类边权的边；
其次，对于只有一类边权的图，每个点 𝑢u 都有一个入度（来自 (𝑢 −𝑦)mod𝑥(u−y)modx）和一个出度（来自 (𝑢 +𝑦)mod𝑥(u+y)modx），因此整个图必然由若干个环构成．并且可以证明共有 gcd(𝑥,𝑦)gcd(x,y) 个等长的环．
证明
设 𝑑 =gcd(𝑥,𝑦)d=gcd(x,y)，设 𝑥 =𝑑𝑎,𝑦 =𝑑𝑏x=da,y=db，有 gcd(𝑎,𝑏) =1gcd(a,b)=1．
考虑从 𝑢u 出发走 𝑘k 步，到达 (𝑢 +𝑘𝑦)mod𝑥(u+ky)modx．若成环，则 𝑘𝑦 ≡0(mod𝑥)ky≡0(modx)，即有 𝑘𝑏 ≡0(mod𝑎)kb≡0(moda)．
由于 gcd(𝑎,𝑏) =1gcd(a,b)=1，最小的 𝑘 =𝑎k=a，即环长为 𝑎 =𝑥𝑑a=xd．由于是从任意点开始，故每个可能的环长相等，环的数量为 𝑑d．
并且，边权为正，绕环两圈后，一定不能继续松弛．直接循环更新一遍就行了．这样处理就不会受限于最短路的复杂度，可以做到 𝑂(𝑥)O(x)．
与差分约束问题相同，当存在一组解 {𝑎1,𝑎2,⋯,𝑎𝑛}{a1,a2,⋯,an} 时，{𝑎1 +𝑑,𝑎2 +𝑑,⋯,𝑎𝑛 +𝑑}{a1+d,a2+d,⋯,an+d} 同样为一组解，因此在该题让 𝑖 =1i=1 作为源点，此时源点处的 𝑑𝑖𝑠1 =1dis1=1 在已知范围内最小，因此得到的也是一组最小的解．
答案即为：
𝑥−1∑𝑖=0(ℎ−𝑑𝑖𝑥+1)∑i=0x−1(h−dix+1)
加 1 是由于 𝑑𝑖di 所在楼层也算一次．
代码实现上注意到 ℎh 的范围是 ℎ ≤263 −1h≤263−1，所以在求解最短路之前 𝑑𝑖di 的初始值应至少设为 263263，这超过了 C++ 中 `long long` 的最大值．所以可以使用 `unsigned long long` 或者先把 ℎ ←ℎ −1h←h−1，然后把最低楼层设为 00 层，其他代码无异．
基于环优化的实现
---|---
例题二
题目大意：给定 𝑛n，求 𝑛n 的倍数中，数位和最小的那一个的数位和．（1 ≤𝑛 ≤1051≤n≤105）
本题可以使用循环卷积优化完全背包在 𝑂(𝑛log2𝑛)O(nlog2n) 的时间内解决，但我们希望得到线性的算法．
观察到任意一个正整数都可以从 11 开始，按照某种顺序执行乘 1010、加 11 的操作，最终得到，而其中加 11 操作的次数就是这个数的数位和．这提示我们使用最短路．
对于所有 0 ≤𝑘 ≤𝑛 −10≤k≤n−1，从 𝑘k 向 10𝑘10k 连边权为 00 的边；从 𝑘k 向 𝑘 +1k+1 连边权为 11 的边．（点的编号均在模 𝑛n 意义下）
每个 𝑛n 的倍数在这个图中都对应了 11 号点到 00 号点的一条路径，求出 11 到 00 的最短路即可．某些路径不合法（如连续走了 1010 条边权为 11 的边），但这些路径产生的答案一定不优，不影响答案．
时间复杂度 𝑂(𝑛)O(n)．
习题
[[国家集训队] 墨墨的等式](https://www.luogu.com.cn/problem/P2371)
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Enter-tainer, Xeonacid, Jijidawang, R-G-Mocoratioen, TenilTen, CCXXXI, ChungZH, F1shAndCat, kenlig, Menci, ShaoChenHeng, shuzhouliu, Tiphereth-A, XuYueming520, zhangletao 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用