BZOJ 2118: 墨墨的等式

2118: 墨墨的等式

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 1656 Solved: 650
[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

Sample Output

HINT

对于100%的数据，N≤12，0≤ai≤5*10^5，1≤BMin≤BMax≤10^12。

Source

分析：

考虑只能有非负解，所以就是答案就是所有的数字可以组合出来的区间内数字个数...

首先把区间询问转化为前缀和相减的问题...

考虑任取一个大于$0$的数字$a_i$，如果一个数字$x mod a_i=y$可以被这$n$个数字组合出来，那么$x+a_i$、$x+2*a_i$......都可以被组合出来，并且如果不能组合出来，那么这个数字一定不存在解，所有我们只需要求出最小的$x$使得$x mod a_i=y$就好了，这个可以转化为最短路问题...

代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
//by NeighThorn
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;

const int maxn=12+5,maxm=500000+5;

int n,be,a[maxn],vis[maxm];
long long BMin,BMax,dis[maxm];

queue<int> q;

inline void spfa(void){
	for(int i=0;i<a[be];i++) dis[i]=inf;
	dis[0]=0;vis[0]=1;q.push(0);
	while(!q.empty()){
		int top=q.front();q.pop();vis[top]=0;
		for(int i=be,x;i<=n;i++){
			x=(top+a[i])%a[be];
			if(dis[x]>dis[top]+a[i]){
				dis[x]=dis[top]+a[i];
				if(!vis[x])
					q.push(x),vis[x]=1;
			}
		}
	}
}

inline long long calc(long long x){
	long long ans=0;
	for(int i=0;i<a[be];i++)
		if(dis[i]<=x) ans+=(x-dis[i])/a[be]+1;
	return ans;
}

signed main(void){
#ifndef ONLINE_JUDGE
	freopen("equation9.in","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	scanf("%d%lld%lld",&n,&BMin,&BMax);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);be=1;
	sort(a+1,a+n+1);if(!a[n]) {puts("0");return 0;}
	while(a[be]==0) be++;spfa();
	printf("%lld
",calc(BMax)-calc(BMin-1));
	return 0;
}

By NeighThorn