rockdu
2118: 墨墨的等式
Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 2271 Solved: 893
[Submit][Status][Discuss]
Description
墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。
Input
输入的第一行包含3个正整数，分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上界。输入的第二行包含N个整数，即数列{an}的值。
Output
输出一个整数，表示有多少b可以使等式存在非负整数解。
Sample Input
2 5 10
3 5
3 5
Sample Output
5
HINT
对于100%的数据，N≤12，0≤ai≤5*10^5，1≤BMin≤BMax≤10^12。
Source
一波骚操作图论建模加最短路，原理很玄妙啊。鄙人不才（其实是懒(～￣▽￣)～ ），这篇博客就讲的比较清楚 我是“这篇博客”
#include<cstdio>
#include<cstring>
#include<queue>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 5e5 + 5;
const int inf = 0x3f3f3f3f;
struct edge {
int v, w, next;
}e[maxn * 13];
int head[maxn], cnt, n, a[15], ax, vis[maxn];
long long dis[maxn], ans, D, U;
void adde(const int & u, const int & v, const int & w) {
e[cnt] = (edge){v, w, head[u]};
head[u] = cnt++;
}
void SPFA() {
memset(dis, inf, sizeof(dis));
deque<int > q;
q.push_back(0);
dis[0] = 0;
while(!q.empty()) {
int u = q.front();
q.pop_front(), vis[u] = 0;
for(register int i = head[u]; ~i; i = e[i].next) {
if(dis[u] + e[i].w <= dis[e[i].v]) {
dis[e[i].v] = dis[u] + e[i].w;
if(vis[e[i].v]) continue;
if(!q.empty() && dis[e[i].v] <= dis[q.front()]) q.push_front(e[i].v);
else q.push_back(e[i].v);
vis[e[i].v] = 1;
}
}
}
}
int main() {
memset(head, -1, sizeof(head));
scanf("%d%lld%lld", &n, &D, &U);
ax = inf;
For(i, 1, n) scanf("%d", &a[i]), ax = min(ax, a[i]);
For(i, 0, ax - 1)
For(j, 1, n) adde(i, (i + a[j]) % ax, a[j]);
SPFA();
--D;
For(i, 0, ax - 1) {
if(dis[i] <= U) ans += (U - dis[i])/ax + 1;
if(dis[i] <= D) ans -= (D - dis[i])/ax + 1;
}
printf("%lld", ans);
return 0;
}
没有帐号? 立即注册