nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

bzoj2118

Dedivion
墨墨突然对等式很感兴趣，他正在研究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
5

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

---

f[i]表示模x意义下等于i时的最小背包容量
如果我们取x=min(ai),
则对于所有的f[i],f[i]+k*ai一定能够取得到
f用最短路来求即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ll n,l,r;
    scanf("%lld%lld%lld",&n,&l,&r);
    ll mi=1<<30;
    ll a[12];
    for(ll i=0;i<n;i++) {
        scanf("%lld",a+i);
        mi=min(mi,a[i]);
    }
    vector<ll> dis(mi,1e18);
    priority_queue<ll,vector<ll>,greater<ll> > q;
    q.push(0);
    dis[0]=0;
    while(!q.empty()){
        ll u=q.top();q.pop();
        for(ll i=0;i<n;i++){
            ll v=u+a[i];
            if(dis[v%mi]>dis[u%mi]+a[i]) {
                dis[v%mi]=dis[u%mi]+a[i];
                q.push(v);
            }
        }
    }
    l--;
    long long ans=0;
    for(ll i=0;i<mi;i++){
        if(dis[i]<=l) ans-=(l-dis[i])/mi+1;
        if(dis[i]<=r) ans+=(r-dis[i])/mi+1;
    }
    cout<<ans<<endl;
}
// 5 6 8 9 10
// 2 0 2 1 1