相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2118
神犇题解：https://blog.sengxian.com/solutions/bzoj-2118
解题报告
先来看一道简单的题目：
给定$a,b,c(a,b,c \le 10^5)$，规定$x,y,z \in \mathbb{N}$
问$ax+by+cz$不能表示出的正整数中，最大的那一个是多少
我们不妨在$\bmod c$的意义下做，这样就可以只考虑$0 \sim c-1$
于是暴力用$a,b$连边，跑一边最短路
这样就可以求出在$\bmod c$的剩余系中，每一个等价类最早出现的位置
于是扫一遍，取一个$\max$就可以了
然后再看看这个题，也就是多连几条边的事吧？
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 500009;
const int M = N * 12;
const LL INF = 1e17;
int n,a[N],done[N];
int nxt[M],to[M],cost[M],head[N];
LL dis[N],bmn,bmx,mn=INF;
priority_queue<pair<LL,int> > que;
inline void AddEdge(int u, int v, int c) {
static int E = 1; cost[++E] = c;
to[E] = v; nxt[E] = head[u]; head[u] = E;
}
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
inline void Dijkstra() {
for (int i=0;i<mn;i++) dis[i] = INF;
dis[0] = 0; que.push(make_pair(0, 0));
while (!que.empty()) {
int w = que.top().second; que.pop();
if (done[w]) continue; else done[w] = 1;
for (int i=head[w];i;i=nxt[i]) {
if (dis[to[i]] > dis[w] + cost[i]) {
dis[to[i]] = dis[w] + cost[i];
que.push(make_pair(-dis[to[i]], to[i]));
}
}
}
}
inline LL cal(LL lim) {
LL ret = 0, tmp;
for (int i=0;i<mn;i++) {
if (lim < dis[i]) continue;
ret += (lim - dis[i]) / mn + 1;
}
return ret;
}
int main() {
n = read(); cin>>bmn>>bmx;
for (int i=1;i<=n;i++) {
a[i] = read();
if (a[i]) mn = min(mn, (LL)a[i]);
}
for (int i=1;i<=n;i++) {
if (a[i] == mn) continue;
for (int j=0;j<mn;j++) {
AddEdge(j, (j+a[i])%mn, a[i]);
}
}
Dijkstra();
printf("%lld\n",cal(bmx)-cal(bmn-1));
return 0;
}
