本文主要是介绍【ZOJ 3887】LCGCDS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
比赛的时候没有想出来跪了（事实上赛后也拖到现在才A掉，还是因为昨天多校有一个加强版的题才想到的）。
题目大意是给你两个序列，问你最长的gcd相同的子串的长度是多少，并且输出个数。
对于每一个以i为结尾的子串，最多只会出现log级别的不同的gcd子串，因此我们可以考虑先把两个序列的gcd长度处理出来，然后再处理。
对于所有gcd为v的子串，我们得到的是很多个最小长度和最大长度的集合。
首先我们先考虑两个集合中能够出现的最大值中的较小值，如果这个值可以被覆盖，则这个值就是gcd为v的子串的最长长度了。
否则就将大的数减小，直到两个集合中都没有数。
具体见代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100005;
struct Line{int v,l,r;Line(){}Line(int v,int l,int r):v(v),l(l),r(r){}bool operator < (const Line &a)const{if(v != a.v) return v < a.v;if(r != a.r) return r < a.r;return l > a.l;}void out(){printf("DDD %d %d %d\n",v,l,r);}
}l1[N * 10],l2[N * 10];
int gcd(int a,int b){return b == 0 ? a : gcd(b,a % b);
}
int n,m;
int a[N],b[N];
int val[N],tp[N];
int calc(int s1,int e1,int s2,int e2){while(s1 <= e1 && s2 <= e2){if(l1[e1].r > l2[e2].r){if(l1[e1].l <= l2[e2].r)return l2[e2].r;else e1 --;}else if(l1[e1].r < l2[e2].r){if(l2[e2].l <= l1[e1].r)return l1[e1].r;else e2 --;}else return l1[e1].r;}return -1;
}
void solve(){int cnt1 = 0,cnt2 = 0;for(int i = 1 ; i <= n ; i ++) scanf("%d",&a[i]);for(int i = 1 ; i <= m ; i ++) scanf("%d",&b[i]);val[1] = a[1];tp[1] = 1;l1[cnt1 ++] = Line(val[1],1,1);for(int i = 2 ; i <= n ; i ++){val[i] = a[i];tp[i] = i;int t = tp[i];while(t){val[t] = gcd(val[t],a[i]);while(tp[t] - 1 && gcd(val[t],val[ tp[t] - 1 ]) == val[t])tp[t] = tp[ tp[t] - 1 ];l1[cnt1 ++] = Line(val[t],i - t + 1,i - tp[t] + 1);t = tp[t] - 1;}}val[1] = b[1];tp[1] = 1;l2[cnt2 ++] = Line(val[1],1,1);int lans = -1;for(int i = 2 ; i <= m ; i ++){val[i] = b[i];tp[i] = i;int t = tp[i];while(t){val[t] = gcd(val[t],b[i]);while(tp[t] - 1 && gcd(val[t],val[ tp[t] - 1 ]) == val[t])tp[t] = tp[ tp[t] - 1 ];l2[cnt2 ++] = Line(val[t],i - t + 1,i - tp[t] + 1);t = tp[t] - 1;}}sort(l1,l1 + cnt1);sort(l2,l2 + cnt2);/*for(int i = 0 ; i < cnt1 ; i ++) l1[i].out();printf("****\n");for(int i = 0 ; i < cnt2 ; i ++) l2[i].out();*/int s1,s2,e1,e2;s1 = s2 = 0;e1 = e2 = -1;for(int i = 0 ; i < cnt1 ; i ++){s1 = e1 = i;while(e1 + 1 < cnt1 && l1[e1 + 1].v == l1[s1].v) e1 ++;while(s2 < cnt2 && l2[s2].v < l1[s1].v) s2 ++,e2 ++;if(l2[s2].v != l1[s1].v){i = e1;continue;}while(e2 + 1 < cnt2 && l2[e2 + 1].v == l2[s2].v) e2 ++;if(s2 == cnt2) break;if(s2 <= e2) lans = max(lans,calc(s1,e1,s2,e2));i = e1;s2 = e2 + 1;}if(lans == -1){printf("0 0\n");return;}s1 = s2 = 0;e1 = e2 = -1;int c1,c2;LL vans = 0;for(int i = 0 ; i < cnt1 ; i ++){s1 = e1 = i;while(e1 + 1 < cnt1 && l1[e1 + 1].v == l1[s1].v) e1 ++;while(s2 < cnt2 && l2[s2].v < l1[s1].v) s2 ++,e2 ++;if(l2[s2].v != l1[s1].v){i = e1;continue;}while(e2 + 1 < cnt2 && l2[e2 + 1].v == l2[s2].v) e2 ++;if(s2 == cnt2) break;c1 = c2 = 0;for(int j = s1 ; j <= e1 ; j ++)if(l1[j].l <= lans && lans <= l1[j].r) c1 ++;for(int j = s2 ; j <= e2 ; j ++)if(l2[j].l <= lans && lans <= l2[j].r) c2 ++;vans += 1ll * c1 * c2;i = e1;s2 = e2 + 1;}printf("%d %lld\n",lans,vans);
}
int main()
{while(~scanf("%d%d",&n,&m)) solve();return 0;
}这篇关于【ZOJ 3887】LCGCDS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
