BZOJ_2118_墨墨的等式_最短路

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。

首先将L，R差分，求[1,x]有多少符合条件的数。

但是x太大，考虑将x%min{ai}，这样我们求的x就变成500000以内的了。

设dis[i]表示长度为b且b%mina=i且最小的b。

也就是我们对于每个模之后的数求一个最小能表示的，然后就能求出有多少个可以表示的了。

代码：

#include <cstdio>

#include <string.h>

#include <algorithm>

#include <ext/pb_ds/priority_queue.hpp>

using namespace std;

using namespace __gnu_pbds;

#define N 500050

typedef long long ll;

ll dis[N],L,R;

int n,minl,a[20],vis[N];

__gnu_pbds::priority_queue<pair<ll,int> >q;

ll solve(ll x) {

    ll re=0;

    int i;

    for(i=0;i<minl;i++) {

        if(dis[i]<=x) {

            re+=(x-dis[i])/minl+1;

        }

    }

    return re;

}

int main() {

    scanf("%d%lld%lld",&n,&L,&R);

    int i;

    minl=1<<30;

    for(i=1;i<=n;i++) {

        scanf("%d",&a[i]);

        minl=min(minl,a[i]);

    }

    memset(dis,0x3f,sizeof(dis));

    dis[0]=0; q.push(make_pair(0,0));

    while(!q.empty()) {

        int x=q.top().second; q.pop();

        if(vis[x]) continue;

        vis[x]=1;

        ll v=dis[x];

        for(i=1;i<=n;i++) {

            if(dis[(v+a[i])%minl]>v+a[i]) {

                dis[(v+a[i])%minl]=v+a[i];

                q.push(make_pair(-dis[(v+a[i])%minl],(v+a[i])%minl));

            }

        }

    }

    printf("%lld\n",solve(R)-solve(L-1));

}

秒客网