---

2118: 墨墨的等式

　　Time Limit: 10 Sec
　　Memory Limit: 259 MB

Description

　　墨墨突然對等式很感興趣，他正在研究a1x1+a2y2+…+anxn=B存在非負整數解的條件，他要求>你編寫一個程序，給定N、{an}、以及B的取值范圍，求出有多少B可以使等式存在非負整數解。
　　　

Input

　　輸入的第一行包含3個正整數，分別表示N、BMin、BMax分別表示數列的長度、B的下界、B的上界。
　　輸入的第二行包含N個整數，即數列{an}的值。
　　

Output

　　輸出一個整數，表示有多少b可以使等式存在非負整數解。
　　

Sample Input 1

　　2 5 10
　　3 5
　　

Sample Output 1

　　5
　　

HINT

　　對于100%的數據，N≤12，0≤ai≤5*10^5，1≤BMin≤BMax≤10^12。
　　

題目地址：　BZOJ 2118: 墨墨的等式

題解：

　　 　　
　　每個數都能表示成\(k*a[1]+x(0<=x<a[1])\)的形式
　　如果對于每個\(x\)我們求出最小的\(k*a[1]+x\)
　　那么把\([l,r]\)分成\([1,l-1]\)和\([1,r]\)來做，就可以輕松統計答案
　　問題就變成了如何求出最小的\(k*a[1]+x\)
　　把每個\(x\)都當做一個點
　　只需在\(x\)和\((x+a[j])\) mod \(a[1]\)之間連一條邊權為\(a[j]\)的邊，再跑一遍最短路即可
www.cnblogs.com/AGFghy/

---

AC代碼

#include<cstdio> #include<algorithm> #include<queue> #define pa pair<ll,int> using namespace std; typedef long long ll; int n,num,now; int len[6000005],point[6000005],next[6000005],p[500005],head[500005],a[20]; ll d[500005]; ll l,r,nl,nr; void insert(int u,int v,int l) {num++; len[num]=l; point[num]=v; next[num]=head[u]; head[u]=num; } void Dijkstra(int x) {priority_queue<pa,vector<pa>,greater<pa> >q; for (int i=0; i<=a[now]-1; i++)d[i]=(ll)1e60,p[i]=0;d[x]=0; q.push(make_pair(0,x));while (!q.empty()){int now=q.top().second; p[now]=1;q.pop();for (int i=head[now]; i; i=next[i]){int v=point[i];if (p[v]) continue;if (d[now]+len[i]<d[v]){d[v]=d[now]+len[i];q.push(make_pair(d[v],v));}}} } int main() {scanf("%d%lld%lld",&n,&l,&r);l--;for (int i=1; i<=n; i++)scanf("%d",&a[i]);sort(a+1,a+n+1);now=1;while (a[now]==0) now++;for (int i=0; i<=a[now]-1; i++)for (int j=2; j<=n; j++)insert(i,(i+a[j])%a[now],a[j]);Dijkstra(0);for (int i=0; i<=a[now]-1; i++)if (d[i]<=r){if (l-d[i]>=0) nl+=((l-d[i])/a[now])+1;if (r-d[i]>=0) nr+=((r-d[i])/a[now])+1;}printf("%lld\n",nr-nl); }

轉載于:https://www.cnblogs.com/AGFghy/p/9366363.html

總結

以上是生活随笔為你收集整理的BZOJ 2118: 墨墨的等式（最短路dijkstra+堆）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。