同余类最短路 笔记

未分类

给定 $B$ 的取值范围，求使得 $n$ 元一次方程 $\sum\limits_{i=1}^{n} a_ix_i=B$ 有非负整数解的 $B$ 的个数。

很明显如果 $\sum\limits_{i=1}^n a_ix_i=g$，则 $g$ 加上任意一个 $a_i$ 也能使得方程有非负整数解。转化为如 $g \bmod \mbox{任意一个a}+{任意个a}$ 使方程有非负整数解则 $g$ 也可以。那么对于任意一个 $a_i$ 的剩余系来讨论，设 $dist(x)$ 满足 $dist(x) \bmod a_i=x$，$dist(x)$ 可以使得方程有非负整数解且 $dist(x)$ 最小，那么就可以看成是一个最短路模型，求出所有的 $dist(i),0\leq i \leq a_i$，如果 $dist(b \bmod a_i)\leq b$，$b$ 就满足条件。为了使速度最快选择最小的 $a_i$，将答案转化为前缀和相减的形式计算即可。为什么这样算出的答案不重不漏呢？因为这里的每个 $dist(x)$ 必然只能构造出 $m$ 的系数为 $0$ 的解，然后再用这个数统计 $m$ 的系数不为 $0$ 的解，所以不重不漏。

这里放上模板题 Luogu2371 墨墨的等式 的代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
typedef long long LL;
#define int long long
const int MAXN = 20;
const int MAXA = 5e5;
int n, m, b_max, b_min;
int a[MAXN | 1], fst[MAXN | 1], dist[MAXA];
struct Queue {
  int dis, x;
  Queue() : dis(0), x(0) {}
  Queue(int a, int b) : x(a), dis(b) {}
  friend bool operator< (const Queue &lhs, const Queue &rhs) {
    return lhs.dis > rhs.dis;
  }
};
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
void Dijkstra() {
  memset(dist, 0x3f, sizeof(dist));
  dist[0] = 0;
  std::priority_queue < Queue > q;
  q.push(Queue(0, 0));
  do {
    Queue from = q.top();
    q.pop();
    if (dist[from.x] != from.dis) continue;
    for (int i = 1; i <= n; ++i) {
      int to = (from.x + a[i]) % m, w = a[i];
      if (dist[to] > dist[from.x] + w) {
        dist[to] = dist[from.x] + w;
        q.push(Queue(to, dist[to]));
      }
    }
  } while (!q.empty());
}
LL query(LL x) {
  LL res = 0;
  for (int i = 0; i < m; ++i) 
    if (dist[i] <= x) 
      res += (x - dist[i]) / m + 1;
  return res;
}
signed main() {
  freopen("code.in", "r", stdin);
  freopen("code.out", "w", stdout);
  n = read();
  scanf("%lld %lld", &b_min, &b_max);
  m = 1e9;
  for (int i = 1; i <= n; ++i) a[i] = read(), m = std::min(m, a[i]);
  Dijkstra();
  printf("%lld\n", query(b_max) - query(b_min - 1));
  return 0;
}