正題

題目鏈接:https://www.luogu.com.cn/problem/P2371

---

題目大意

$n$個$a_i$，求有多少個$b\in [l,r]$滿足${\sum }_{i=1}^n{a}_i{x}_i=b$有正整數解。

---

解題思路

因為有一個$a_1$在，而且$x_1$可以是任意正整數，所以如果在$b$很大的情況下，能夠湊出一個數$k$使得$k\%a_1=b\%a_1$那就能湊出$b$。

所以我們設$f_i$表示能湊出的最小的$k$使得$k\%a_1=i$。然后最短路轉移即可。

時間復雜度$O(a_{1}n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define ll long long using namespace std; const ll N=5e5+10; struct node{ll to,next,w; }a[N*20]; struct point{ll x,dis; }; bool operator<(point x,point y) {return x.dis>y.dis;} priority_queue<point> q; ll n,m,l,r,tot,f[N],ls[N],w[N]; bool v[N]; void addl(ll x,ll y,ll w){a[++tot].to=y;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot;return; } void Dij(){memset(f,0x3f,sizeof(f));f[0]=0;q.push((point){0,0});while(!q.empty()){ll x=q.top().x;q.pop();if(v[x])continue;v[x]=1;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(f[x]+a[i].w<f[y]){f[y]=f[x]+a[i].w;if(!v[y])q.push((point){y,f[y]});}}}return; } ll get(ll x){ll ans=0;for(ll i=0;i<m;i++)if(x>=f[i])ans+=(x-f[i])/m+1;return ans; } int main() {scanf("%lld%lld%lld",&n,&l,&r);for(ll i=1;i<=n;i++)scanf("%lld",&w[i]);for(ll i=1;i<=n;i++)if(!w[i])swap(w[i],w[n]),n--;sort(w+1,w+1+n);m=w[1];for(ll i=2;i<=n;i++){for(ll j=0;j<m;j++)addl(j,(j+w[i])%m,w[i]);}Dij();printf("%lld",get(r)-get(l-1)); }

總結

以上是生活随笔為你收集整理的P2371-[国家集训队]墨墨的等式【同余最短路】的全部內容，希望文章能夠幫你解決所遇到的問題。

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