同余最短路 学习笔记

当出现形如「给定 $n$ 个整数，求这 $n$ 个整数能拼凑出多少的其他整数（$n$ 个整数可以重复取）」，以及「给定 $n$ 个整数，求这 $n$ 个整数不能拼凑出的最小（最大）的整数」，或者「至少要拼几次才能拼出模 $K$ 余 $p$ 的数」的问题时可以使用同余最短路的方法。

同余最短路利用同余来构造一些状态，可以达到优化空间复杂度的目的。

类比 差分约束 方法，利用同余构造的这些状态可以看作单源最短路中的点。同余最短路的状态转移通常是这样的 $f(i+y)=f(i)+y$，类似单源最短路中 $f(v)=f(u)+edge(u,v)$。

例题

例题一

NOTE

P3403 跳楼机

题目大意：给定 $x，y，z，h$，对于 $k\in [1,h]$，有多少个 $k$ 能够满足 $ax+by+cz=k$。（$0\le a,b,c$，$1\le x,y,z\le {10}^5$，$h\le 2^{63}-1$）

不妨假设 $x<y<z$。

令 $d_i$ 为只通过 操作 2 和 操作 3，需满足 $pmodx=i$ 能够达到的最低楼层 $p$，即 操作 2 和 操作 3 操作后能得到的模 $x$ 下与 $i$ 同余的最小数，用来计算该同余类满足条件的数个数。

可以得到两个状态：

• $i\stackrel{y}{\to }(i+y)modx$

• $i\stackrel{z}{\to }(i+z)modx$

注意通常选取一组 $a_i$ 中最小的那个数对它取模，也就是此处的 $x$，这样可以尽量减小空间复杂度（剩余系最小）。

那么实际上相当于执行了最短路中的建边操作：

add(i, (i+y) % x, y)

add(i, (i+z) % x, z)

接下来只需要求出 $d_0,d_1,d_2,\dots ,d_{x-1}$，只需要跑一次最短路就可求出相应的 $d_i$。

但是事实上也不需要进行正常的最短路求解，注意到有两个特殊的性质：

首先，只有两种边权，且对于每一条路径，由于加法交换律，走两种边权的顺序是无影响的。因此可以考虑做两次最短路，每次只建出一类边权的边；

其次，对于只有一类边权的图，每个点 $u$ 都有一个入度（来自 $(u-y)modx$）和一个出度（来自 $(u+y)modx$），因此整个图必然由若干个环构成。并且可以证明共有 $gcd(x,y)$ 个等长的环。

NOTE

证明

设 $d=gcd(x,y)$，设 $x=da,y=db$，有 $gcd(a,b)=1$。

考虑从 $u$ 出发走 $k$ 步，到达 $(u+ky)modx$。若成环，则 $ky\equiv 0(\mathrm{mod}x)$，即有 $kb\equiv 0(\mathrm{mod}a)$。

由于 $gcd(a,b)=1$，最小的 $k=a$，即环长为 $a={\displaystyle \frac{x}{d}}$。由于是从任意点开始，故每个可能的环长相等，环的数量为 $d$。

并且，边权为正，绕环两圈后，一定不能继续松弛。直接循环更新一遍就行了。这样处理就不会受限于最短路的复杂度，可以做到 $O(x)$。

与差分约束问题相同，当存在一组解 $\{a_1,a_2,\cdots ,a_n\}$ 时，$\{a_1+d,a_2+d,\cdots ,a_n+d\}$ 同样为一组解，因此在该题让 $i=1$ 作为源点，此时源点处的 $di{s}_1=1$ 在已知范围内最小，因此得到的也是一组最小的解。

答案即为：

$$\sum _{i=0}^{x-1}(\frac{h-d_i}{x}+1)$$

加 1 是由于 $d_i$ 所在楼层也算一次。

代码实现上注意到 $h$ 的范围是 $h\le 2^{63}-1$，所以在求解最短路之前 $d_i$ 的初始值应至少设为 $2^{63}$，这超过了 C++ 中 long long 的最大值。所以可以使用 unsigned long long 或者先把 $h\leftarrow h-1$，然后把最低楼层设为 $0$ 层，其他代码无异。

例题二

NOTE

ARC084B Small Multiple 题目大意：给定 $n$，求 $n$ 的倍数中，数位和最小的那一个的数位和。（$1\le n\le {10}^5$）

本题可以使用循环卷积优化完全背包在 $O(n{\log }^{2}n)$ 的时间内解决，但我们希望得到线性的算法。

观察到任意一个正整数都可以从 $1$ 开始，按照某种顺序执行乘 $10$、加 $1$ 的操作，最终得到，而其中加 $1$ 操作的次数就是这个数的数位和。这提示我们使用最短路。

对于所有 $0\le k\le n-1$，从 $k$ 向 $10k$ 连边权为 $0$ 的边；从 $k$ 向 $k+1$ 连边权为 $1$ 的边。（点的编号均在模 $n$ 意义下）

每个 $n$ 的倍数在这个图中都对应了 $1$ 号点到 $0$ 号点的一条路径，求出 $1$ 到 $0$ 的最短路即可。某些路径不合法（如连续走了 $10$ 条边权为 $1$ 的边），但这些路径产生的答案一定不优，不影响答案。

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