同余最短路

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

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

类比

差分约束 方法，利用同余构造的这些状态可以看作单源最短路中的点。同余最短路的状态转移通常是这样的 ，类似单源最短路中 。

例题

例题一

不妨假设 。

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

可以得到两个状态：

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

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

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

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

接下来只需要求出 ，只需要跑一次最短路就可求出相应的 。

与差分约束问题相同，当存在一组解 时， 同样为一组解，因此在该题让 作为源点，此时源点处的 在已知范围内最小，因此得到的也是一组最小的解。

答案即为：

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

例题二

本题可以使用循环卷积优化完全背包在 的时间内解决，但我们希望得到线性的算法。

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

对于所有 ，从 向 连边权为 的边；从 向 连边权为 的边。（点的编号均在模 意义下）

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

时间复杂度 。

习题

洛谷 P3403 跳楼机

洛谷 P2662 牛场围栏

[国家集训队]墨墨的等式

「NOIP2018」货币系统

AGC057D - Sum Avoidance