同余最短路

余同最短路。
最短路我们学过，那同余最短路又是什么东西呢？？可以用来解决什么问题？？往下看。
我们从一道题来得到这个算法的思路。
T494899 硬币问题

正宗的同余最短路

有 \(n\) 种面值的硬币（每种有无限枚），问使用这些硬币能够凑出 \([1,m]\) 的多少种金额。\(n \le 100,m \le 10^{12},w_i \le 10^6\)。
显然这个东西可以使用完全背包做。这样是 \(O(nm)\) 的，可是缺点太大。
于是，一个很神奇的解决方法就出现了：同余最短路。
我们观察一个性质：如果对于某一个 \(w_i\)，如果 \(x\) 是可以通过若干面额凑出来的，则 \(x+w_i\) 也一定可以凑出来。
所以对于 \(x \bmod w_i = d\) 的情况，如果能够找到可以凑出来的 \(x\) 的最小值，则就可以通过数学方式计算出 \([1,m]\) 中的所有 \(\bmod w_i = d\) 的合法方案数。
具体地，根据左边界可以得出 \(x + k \times w_i \ge 1\)，根据右边界可以得出 \(x + k \times w_i \le m\)，其中 \(k\) 是一个自然数。
解不等式就可以得出 \(k\) 的区间，也可以 \(O(1)\) 计算出 \(\bmod w_i = d\) 的所有合法方案数。
于是这里的问题就变成了如何找到每种余数下的最小的 \(x\)。这个时候就需要请出我们的同余最短路了。
考虑到直接对于每一个 \(w_i\) 算 \(\bmod w_i = d\) 的合法方案数会算重，很麻烦。
不妨直接使用最小的 \(w_a\)。
可以证明，使用 \(\bmod w_a = d (0 \le d < w_a)\) 的一定是全体的答案。很容易证明，也很容易理解。
考虑从举例来理解这个算法的过程。\(n=3,m=1000,w=\{3,7,8\}\)。
最短路一定是需要建图的。为了便于理解，所以这个时候就建 \(8\) 个点 \(0\) 到 \(7\)，表示对 \(8\) 的余数。
你应该可以猜到最短路就是什么了，没错就是对于 \(8\) 的余数 \(0 \le d \le 7\) 的可以凑出来的最小 \(x\)。
显然 \(0\) 的最短路就是 \(0\)。

虽然这样是不符合条件的因为 $0 > n >> m;        for (int i = 1; i > w;        sort(w + 1, w + n + 1);        Dijkstra(0);        int ans = 0;        for (int i = 0; i < w[1]; ++i)//为了节省时间，所以采用最小的 w_1                if (dis < 1e17 && dis