本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-06 16:28:22

$\sum\limits_{i=1}^n a_ix_i=b$，我们注意到：不等式只能有零个或者无穷多个解。因为若 $b$ 可以使不等式有解，那么我们可以构造出 $b + a_k$，其中 $a_0$ 是 $a$ 的任意一个元素。我们有：

$$a_k\cdot (x_i+1) + \sum\limits_{i=1, i \neq k}^na_ix_i=b+a_k$$

实际上，我们并不需要考虑每一个 $b$，只需要考虑其在 $\mod a_k$ 意义下的情况。因为对于所有 $b \gt a_k$，我们都可以设 $b' = b - a_k$，此时有：

$$a_k\cdot (x_i-1) + \sum\limits_{i=1,i\neq k}^n a_ix_i = b - a_k$$

即，若有 $b \ge a_k$ 可以满足这个不等式，一定可以找到 $b' \in \mod a_k$ 满足这个不等式。

于是我们设 $f(x)$ 代表在 $[x]$ 内满足此不等式的最小值，那么 $f(x) = \min\limits_{i=0}^n f(x - a_i) + a_i$。这和最短路的松弛操作很像。于是我们可以用最短路来做。

求出所有的 $f(x)$ 后，统计根的数量即可。

不得不说这题作为紫的确有点水了，说不定以后会和数位 DP 一样降绿（）