这是本文档旧的修订版！

同余最短路

算法简介

用于计算 $k_1a_1+k_2a_2+\cdots +k_na_n$ 在 $[0,m]$ 范围内不能表示的数的算法。

考虑建点 $0,1\cdots a_1-1$。然后对每个点 $i$，连边 $i\to (i+a_j)\bmod a_1(w=a_j)$，再跑最短路。

于是可以 $O(n\times a\log a)$ 计算出最小的可以表示成 $ka_1+r(0\le r\lt a_1)$ 的数，于是每个 $r$ 对答案的贡献为 $\lfloor \frac {m-\text{dis}(r)}{a_1}\rfloor$。

不难发现 $a_1$ 越小越好，另外每个点的相邻点可以在跑最短路算法时动态计算，这些都有利于卡常。