Description
墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。
Solution
选择任意一个正整数(a_i),作为 (x*a_i) 的底数,然后假如我们知道了最小满足 (B \% a_i=k) 的 (B),那么大于 (B) 的满足与 (B) 同余的也一定能够凑出来
所以我们只需要对于每一个余数,求出 (dis[i]) 表示用 (a_1....a_n) 能够凑出的满足 (B%a_i=i) 的最小的 (B) 为多少
然后对于每一个剩余类,分别算答案即可,可以保证不重不漏
最后答案就是 (solve(BMax)-solve(BMin-1)) 了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=15;
int n,a[N],p=1;ll L,R,dis[500005];
queue<int>Q;bool vis[500005];
inline void spfa(){
for(int i=0;i<a[p];i++)dis[i]=1e13;
dis[0]=0;vis[0]=1;Q.push(0);
while(!Q.empty()){
int x=Q.front();Q.pop();
for(int i=1;i<=n;i++){
int u=(x+a[i])%a[p];
if(dis[x]+a[i]<dis[u]){
dis[u]=dis[x]+a[i];
if(!vis[u])vis[u]=1,Q.push(u);
}
}
vis[x]=0;
}
}
inline ll calc(ll x,int k){
return (x-k)/a[p]+1;
}
inline ll solve(ll mid){
ll ret=0;
for(int i=0;i<a[p];i++)
if(dis[i]<=mid)ret+=calc(mid,i)-calc(dis[i]-1,i);
return ret;
}
int main(){
freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
scanf("%d%lld%lld",&n,&L,&R);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
if(a[n]==0){puts("0");return 0;}
while(!a[p])p++;spfa();
printf("%lld
",solve(R)-solve(L-1));
return 0;
}