05 同余最短路

问题类型

• 给定 $n$ 个整数， 求这些整数可以拼凑出多少的其他整数 （ $n$ 个整数可以重复选择）
• 给定 $n$ 个整数， 求这些整数不能拼凑出的最小 / 最大的整数
• 至少要拼凑几次才能拼出 $modk=p$ 的数

问题求解方案

选择这个整数集合 $A$ 中最小的正整数 $m$ ， 定义一个数组为 $d(i)$ , 表示这些数可以拼凑出的 $modm=i$ 的最小数

由于本身 $m$ 就在集合 $A$ 中，所以就可以得到 $d[i]+k\times m$ 的任何数

转化为图论（最短路求解）模型

迪杰斯特拉， 对于当前最小的 $d[x]$ 去遍历一遍 $A$ ， 尝试更新 $d[(x+a_i)\%m]$ , 知道无法在再有新的更新为止

求答案注意点

对于问题类型 2 中的最大为 $res=max(res,d[i]-m)$
最小为：
如果集合中存在 1 , 那么不存在最小
如果不存在 1 , 那么答案就是最小