本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-29 20:27:41

P2371 为例。

我们可以取一个数 $m \in A$，然后设 $f(k)$ 表示模 $m$ 为 $k$ 时整个式子最小值。

明显有 $x$ 可以转移到 $(x + a_i) \bmod m$，权是 $a_i$。由于有后效性，我们不能直接转移，考虑最短路就可以跑出来。

然后我们可以把 $[l, r]$ 差分成 $[1, r] \cap [1, l - 1]$ 来统计答案。考虑怎么统计 $[1, x]$ 的答案。如果 $f(i) \le x$，那么我们可以把 $f(i)$ 加上任意个 $x$。所以解的数量就是 $\dfrac{x - f(i) + 1}{x} + 1$。

然后统计就行了。