【图论经典题目讲解】洛谷 P2371 墨墨的等式

P2371 墨墨的等式

$\mathrm{Description}$

求解有多少个 $b\in [l,r]$ 满足 ∑ i = 1naixi= b\sum\limits_{i=1}^n a_ix_i=bi=1∑n​ai​xi​=b 存在非负整数解（ xi x_ixi​ 为变量，$a$ 数组给定）。

$\mathrm{Solution}$

$b$ 一定可以表示为 $q+kv$ 的形式，其中 $q\in [0,v)$ 表示余数，$k\in \mathbb{Z}$。

故，思路可以转化为选择合适的 $v$，对于枚举余数 $q\in 0\sim v-1$，求解通过 ∑ i = 1naixi= b\sum\limits_{i=1}^n a_ix_i=bi=1∑n​ai​xi​=b，所能凑出的最小的 $b$，使得 $b$ 模 $v$ 为 $q$。

那么，为了能够不重不漏的计算出所有的 $b$，$v$ 应取 min ⁡ ( ai)\min(a_i)min(ai​)，即 $a$ 数组中的最小值，这样只要能够由题目中的等式凑出的 $b$，就必定能由 $q+kv$ 的形式。（可以感性理解）

下面就是如何能够求解最小的余数为 $q$ 出的 $b$（$q\in [0,v-1]$），这就运用到了 同余最短路。

将余数 $i$ 连一条向 ( i + aj) m o d   v(i+a_j)\bmod v(i+aj​)modv 长度为 aj a_jaj​ 的边，对于每一个 $j\in [1,n]$。这表示从 $i$ 这个余数加入 aj a_jaj​ 后，将会变为的一个新的余数。在这个图中求从 $0$ 号点到所有点的最短路后，对于 $i$ 号点的含义就是凑出余数为 $i$ 的最小的数。

最后，通过前缀和的思想可以得到 $l\sim r$ 的 $b$ 的个数为 $0\sim r$ 的 $b$ 的个数减去 $0\sim l-1$ 的 $b$ 的个数。对于每一个 $i$，设凑数余数为 $i$ 的最小的数为 b′ b’b′，则若当前最高限制为 $x$，则 $b$ 的个数为 ⌊x − b′ v⌋ + 1\lfloor\frac{x-b’}{v}\rfloor+1⌊vx−b′​⌋+1。

$Code$

#include #define int long longusing namespace std;typedef pair<int, int> PII;typedef long long LL;const int SIZE = 5e6 + 10;int N, L, R;int A[20];int h[SIZE], e[SIZE], ne[SIZE], w[SIZE], idx;int Dist[SIZE], Vis[SIZE];void add(int a, int b, int c){e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;}void Dijkstra(int Start){memset(Dist, 0x3f, sizeof Dist);memset(Vis, 0, sizeof Vis);priority_queue<PII, vector<PII>, greater<PII>> Heap;Heap.push({0, Start}), Dist[Start] = 0;while (Heap.size()){auto Tmp = Heap.top();Heap.pop();int u = Tmp.second;if (Vis[u]) continue;Vis[u] = 1;for (int i = h[u]; ~i; i = ne[i]){int j = e[i];if (Dist[j] > Dist[u] + w[i]){Dist[j] = Dist[u] + w[i];Heap.push({Dist[j], j});}}}}signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);memset(h, -1, sizeof h);cin >> N >> L >> R;int Min = 1e18;for (int i = 1; i <= N; i ++){cin >> A[i];if (A[i]) Min = min(Min, A[i]);}for (int i = 0; i < Min; i ++)for (int j = 1; j <= N; j ++)if (A[j] != Min && A[j])add(i, (i + A[j]) % Min, A[j]);Dijkstra(0);int Tot1 = 0, Tot2 = 0;for (int i = 0; i < Min; i ++)if (Dist[i] <= R)Tot1 += (R - Dist[i]) / Min + 1;for (int i = 0; i < Min; i ++)if (Dist[i] < L)Tot2 += (L - 1 - Dist[i]) / Min + 1;cout << Tot1 - Tot2 << endl;return 0;}