吐槽一下BZOJ沒有C++11? 題還是不難的

BZOJ 4921

---

題意

在長度為$ n$的數列中去掉非空的連續一段并保證剩下數字不少于$ 2$

求合法的所有方案中剩下數字的最大公約數的總和

---

$Solution$

記錄一下前后綴$ gcd$

容易發現不同的$ gcd$的數量是$ log$級別的

為寫起來方便用$ map$存即可

---

$ my \ code$

#include<bits/stdc++.h> #define rt register int #define ll long long #define p 998244353 using namespace std; int k,m,n,x,y,z,cnt,ans; int qz[100010],hz[100010],a[100010]; map<int,int>s1,s2; int main(){scanf("%d",&n);for(rt i=1;i<=n;i++)scanf("%d",&a[i]);qz[1]=a[1];for(rt i=2;i<=n;i++)qz[i]=__gcd(qz[i-1],a[i]);hz[n]=a[n];for(rt i=n-1;i>=1;i--)hz[i]=__gcd(hz[i+1],a[i]);ll ans=0;for(rt i=2;i<n;i++)ans+=qz[i]+hz[i];ans%=p;for(rt i=1;i<=n-2;i++)s1[qz[i]]++;for(rt i=n-2;i>=1;i--){s2[hz[i+2]]++;for(map<int,int>::iterator it=s2.begin();it!=s2.end();it++)(ans+=1ll*__gcd(qz[i],(*it).first)*(*it).second%p)%=p;}cout<<ans;return 0; }

?

轉載于:https://www.cnblogs.com/DreamlessDreams/p/10133336.html

總結

以上是生活随笔為你收集整理的BZOJ4921「Lydsy1706月赛」互质序列的全部內容，希望文章能夠幫你解決所遇到的問題。

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