同余最短路

我们从同余的角度考虑问题。我们考虑模 $A_1$ 的每个同余类 $[x]$，一旦我们能用 $A_2,\dots A_n$ 凑出 $[x]$ 中的某个数 $x$，那么 $[x]$ 中的每个大于等于 $x$ 的数都可以凑出，因为可以不断地加 $A_1$。例如，如果 $A=(5,7,11)$，因为 $7$ 和 $11$ 可以凑出 $[3]$ 中的 $18$，所以 $[3]$ 中大于等于 $18$ 的数 $(18,23,28,\dots)$ 都可以被凑出来。这启示我们，只要我们知道每个同余类中能被凑出的最小数，就可以解决问题。

这可以被转化为一个图论问题。我们对于模 $A_1$ 的每个同余类建出一个节点，向它加 $A_i, (i\in[2,n])$ 后的对应节点连一条边，边权为 $A_i$。那么每个同余类中能被凑出的最小数就是从 $[0]$ 到它的最短路的长度。比如上面的例子中，从 $[0]$ 到 $[3]$ 的最短路是 $[0]\underset{7}{\to}[2]\underset{11}{\to}[3]$，最短路长度为 $18$。

同余最短路的核心在于按同余类建节点，按同余类间的转移建边，建图并不只有上面所述的这一种形式。例如，如果建边时边权变为 $1$，可以求每个同余类最少可以用几个数拼凑而成。如果除了加数还有其他的转移方法，也可以建相应的边。