首页 > 代码库 > Codeforces 475D CGCDSSQ(分治)
Codeforces 475D CGCDSSQ(分治)
题意：给你一个序列a[i],对于每个询问xi,求出有多少个(l,r)对使得gcd(al,al+1...ar)=xi.
表面上是询问，其实只要处理出每个可能的gcd有多少个就好了，当左端点固定的时候，随着右端点的移动，gcd必然是单调非增的，而且个数不会超过log(a[i])个，所以总的不同的个数的上界是nlog(ai)，所以求出所有是可行的。
一个分治的做法是这样的，对于一个区间[l,r]，分治成[l,mid],[mid+1,r]求解，然后就是合并，合并的时候首先求以[l,mid]右端点为结束点的gcd，然后是[mid+1,r]的左端点为起始点的gcd，两边for一遍，由于不同的gcd最多只有log(ai)个，所以合并的时候就是log(ai)^2。
所以复杂度大致是这样的 T(n)=2*T(n/2)+log(ai)^2+O(n) 所以大致可以看成是T(n)=2*T(n/2)+O(n)，所以复杂度大致就是nlogn的级别的。
#include <iostream>#include <cstring>#include <string>#include <cstdio>#include <vector>#include <queue>#include <algorithm>#include <map>#include <cmath>using namespace std;#define maxn 110000#define ll long long#define MP make_pairint n;int a[maxn];map<int,ll> m;int gcd(int a,int b){ return a&&b? gcd(b,a%b):a+b;}void solve(int l,int r){ if(r-l<=3){ for(int i=l;i<=r;++i){ int g=a[i]; for(int j=i;j<=r;++j){ g=gcd(g,a[j]); m[g]++; } } return; } int mid=(l+r)>>1; solve(l,mid); solve(mid+1,r); vector<pair<int,ll> > ls; vector<pair<int,ll> > rs; int cur=-1; ll cnt=0; int g=a[mid]; for(int i=mid;i>=l;--i){ g=gcd(g,a[i]); if(g!=cur) { if(cur!=-1) ls.push_back(MP(cur,cnt)); cur=g;cnt=1; } else{ ++cnt; } } ls.push_back(MP(cur,cnt)); cur=-1;cnt=0;g=a[mid+1]; for(int i=mid+1;i<=r;++i){ g=gcd(g,a[i]); if(g!=cur) { if(cur!=-1) rs.push_back(MP(cur,cnt)); cur=g;cnt=1; } else{ ++cnt; } } rs.push_back(MP(cur,cnt)); for(int i=0;i<ls.size();++i){ for(int j=0;j<rs.size();++j){ int g=gcd(ls[i].first,rs[j].first); ll num=ls[i].second*rs[j].second; m[g]+=num; } }}int main(){ while(~scanf("%d",&n)){ for(int i=1;i<=n;++i){ scanf("%d",a+i); } m.clear(); solve(1,n); int q,xi; scanf("%d",&q); while(q--){ scanf("%d",&xi); if(m.count(xi)) printf("%I64d\n",m[xi]); else puts("0"); } } return 0;}
Codeforces 475D CGCDSSQ(分治)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。