首页 > 代码库 > BZOJ2118墨墨的等式[数论 最短路建模]

BZOJ2118墨墨的等式[数论 最短路建模]

2024-08-12 16:00:59   220人阅读

2118: 墨墨的等式

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 1317  Solved: 504
[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。

 

 

sdsc2016晨姐的课件：
  • 首先，答案=ans(Bmax)-ans(Bmin-1)
  • 找出a1到an中的最小值p，则如果可以构造出答案x，就可以构造出答案x+p
  • 所以我们只需要对于每个b(0<=b<p)，计算出最小的k，使k*p+b能够能够被构造出来，那么对于k’(k’>k) k’*p+b也能构造出来
  • 所以对于每个b建一个点，对于每个ai，从b向(b+ai)%p连一条长度为ai的边
 
模p之后再建图，好厉害
注意计算答案贡献那里，/d[i]的话有蜜汁re
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <queue>using namespace std;typedef long long ll;const ll N=5*1e5+5,INF=1e19;ll n;ll p=INF,a[20];;ll bmx,bmn,ans=0;struct edge{    ll v,w,ne;}e[N*15];ll h[N],cnt=0;void ins(ll u,ll v,ll w){    cnt++;    e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;    //cnt++;    //e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;}void buildGraph(){    for(ll i=0;i<p;i++)        for(ll j=1;j<=n;j++){            if(a[j]==p) continue;            ins(i,(i+a[j])%p,a[j]);            //prllf("ins %d %lld %lld\n",i,(i+a[j])%p,a[j]);        }}struct hn{    ll u,d;    bool operator <(const hn &rhs)const{return d>rhs.d;}};ll d[N];bool done[N];priority_queue<hn> q;void dijkstra(ll s){    for(ll i=0;i<p;i++) d[i]=INF;    d[s]=0;q.push((hn){s,0});    while(!q.empty()){        hn x=q.top();q.pop();        ll u=x.u;        if(done[u]) continue;        done[u]=1;        for(ll i=h[u];i;i=e[i].ne){            ll v=e[i].v;            if(d[v]>d[u]+e[i].w){                d[v]=d[u]+e[i].w;                q.push((hn){v,d[v]});            }        }    }}int main() {    scanf("%lld%lld%lld",&n,&bmn,&bmx);    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]),p=min(p,a[i]);    buildGraph();    dijkstra(0);    for(ll i=0;i<p;i++){        if(d[i]>bmx) continue;        ll l=max(0LL,(bmn-d[i])/p),r=(bmx-d[i])/p;        if(l*p+d[i]<bmn) l++;        ans+=r-l+1;    }    printf("%lld",ans);    return 0;}

 

BZOJ2118墨墨的等式[数论 最短路建模]


联系
我们