概念
同余最短路是一种优化最短路建图的方法
通常是解决给定 (m) 个整数，求这 (m) 个整数能拼凑出多少的其他整数(这 (m) 个整数可以重复取)或给定 (m) 个整数，求这 (m) 个整数不能拼凑出的最小（最大）的整数。
栗题
题目大意：
对于 (sum_{i = 1}^na_ix_i = b) ，给定 (n) ，(a_{1…n}) ，(l)， (r) ，求有多少 (b in[l, r]) 可以使得等式存在非负整数解
(nleq 12,0leq a_ileq5*10^5,0leq lleq rleq 10^{12})
solution
把题目稍微变一下形
求有多少组 (x_i) ，使得 (a_1*x_1 + a_2 * x_2…a_n*x_n = b) 成立
发现这个题和货币系统那个题很像，考虑完全背包做法，但是这个题的 (l, r) 很大，所以就有了同余最短路。
好像题解解释的都不是很清楚 ？？这用分组的思想感觉解释好像能解释的更清楚点 = =
对于这个题，我们可以先求出 ([1, l - 1]) 有多少 (b) 满足条件，再求出 ([1, r]) 有多少 (b) 满足条件，作差就好了。
转换一下，与其考虑 (b) 是否满足条件，不如考虑 (b) 是否能被凑出来。
好，现在我们的目标就是统计 ([1，x]) 内有多少个数能被凑出来。
考虑这么一件事：找出 (a_i) 中最小的记为 (Min) ，令 (p in[1, Min))；
我们所有的数按照对 (Min) 取模，按照余数分为 (Min) 类。
如果 (p + k*Min) 能够被凑出来，那么 (p + (k + N^*) * Min) 也一定能被凑出来，也就是从这之后，这一类都能被凑出来了，令 (tmp = p + k_{min} * Min) ，也就是这一类最早能被凑出来的数。如果 (tmp leq x)，那么这个区间关于这一类能凑出来的数的个数就是 (frac{x - tmp}{Min} + 1) ，求所有类就是对每一类数做相同操作加和就好了。
现在就只剩怎么求每一类被第一次凑出来的数是多少。
把它放在图里，让 (p) 向 ((p +a_i) \% Min) 连一条权值为 (a_i) 有向边，也就是说凑出 (p + a_i) 的代价为 (a_i) ，从 (0) 点到 ([0, Min)) 的最短路长度就是每一类第一次被凑出来的数是多少。
然后就完成啦。
code
/*
work by:Ariel_
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#define int long long
#define rg register
using namespace std;
const int N = 5e5 + 5;
const int M = 6e6 + 5;
const int INF = 0x3f3f3f3f3f3f;
int read(){
int x = 0,f = 1; char c = getchar();
while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
return x*f;
}
int n, l, r, a[N], m, Min = INF, dis[N], vis[N];
struct edge {int v, nxt, w;}e[M];
int head[N], E;
void add_edge(int u, int v, int w) {
e[++E] = (edge) {v, head[u], w};
head[u] = E;
}
queue<int> q;
void SPFA(int s) {
memset(dis, INF, sizeof dis);
dis[s] = 0, q.push(s);
while(!q.empty()) {
int u = q.front(); q.pop(); vis[u] = 0;
for (rg int i = head[u]; i; i = e[i].nxt){
int v = e[i].v, w = e[i].w;
if (dis[v] > dis[u] + e[i].w){
dis[v] = dis[u] + e[i].w;
if (!vis[v]) q.push(v), vis[v] = 1;
}
}
}
}
int query(int x) {
int res = 0;
for (rg int i = 0; i < Min; i++)
if (dis[i] <= x)
res += (x - dis[i]) / Min + 1;
return res;
}
signed main(){
n = read(), l = read(), r = read();
for (rg int i = 1, x; i <= n; i++) {
x = read();
if (x) a[++m] = x, Min = min(x, Min);//0 边没有贡献
}
n = m;
for (rg int i = 0; i < Min; i++)
for (rg int j = 1; j <= n; j++)
if (a[j] != Min) add_edge(i, (i + a[j]) % Min, a[j]);
SPFA(0);
printf("%lld", query(r) - query(l - 1));
puts("");
return 0;
}
这道题的弱化版 P3403 跳楼机
注意这道题是从一楼开始，想想与上面板子比较哪里变了 = =
(finish)