BZOJ2118: 墨墨的等式（同余类BFS）（数学转为图论题）

2118: 墨墨的等式

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

5

HINT

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

思路：这一类问题呢，都可以用同余类DFS来做：首先，我们找到最小的数A，以它作为基准，然后找到关于A的剩余系[0,A-1]的每个数，能用a组合到的最小数。

由于A是最小，而且我们找到了每个数x的最小表示距离dis[x]，那么[0,R]这个区间能表示到的关于A剩余x的个数=(R-dis[x])/A+1;

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=;

const ll inf=1e18;

int a[],N,vis[maxn],A;ll dis[maxn],ans,L,R;

void SPFA()

{

    for(int i=;i<A;i++) dis[i]=inf; dis[]=;

    queue<int>q; q.push(); vis[]=;

    while(!q.empty()){

        int u=q.front(); q.pop();

        for(int i=;i<=N;i++){

            int v=(a[i]+u)%A;

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

                dis[v]=dis[u]+a[i];

                if(!vis[v]) q.push(v),vis[v]=;

            }

        }

        vis[u]=;

    }

}

int main()

{

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

    for(int i=;i<=N;i++){

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

        if(a[i]==) i--,N--;

    }

    nth_element(a+,a+,a+N+);

    L--; A=a[]; SPFA();

    for(int i=;i<a[];i++){

        if(dis[i]==inf) continue;

        if(R>=dis[i]) ans+=(R-dis[i])/A+;

        if(L>=dis[i]) ans-=(L-dis[i])/A+;

    }

    printf("%lld\n",ans);

    return ;

}