CF2005D Alter the GCD 题解

· · 题解

有如下经典结论：设 g_i 为 a_i 的前/后缀 \gcd ，则 g_i 的取值只有 O(\log V) 种。

考虑 l 从右向左做扫描线。

设：

ga_i=\gcd(a_l,\cdots,a_i),gb_i=\gcd(b_l,\cdots,b_i) fa_i=\gcd(a_{i+1},\cdots,a_n),fb_i=\gcd(b_{i+1},\cdots,b_n)

动态维护 ga_i,gb_i 和本质不同的数对 (ga_i,gb_i,fa_i,fb_i)。

显然只有 O(\log V) 对。

且是一个不断单点删除，前缀加数的过程。

使用链表维护，时间复杂度 O(n\log^2V)。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int a[N],b[N],R[N],qa[N],qb[N],ga[N],fa[N],gb[N],fb[N],n,ans;
long long cnt;
void solve()
{
    ans=cnt=0;
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i],qa[i]=__gcd(qa[i-1],a[i]),ga[i]=gb[i]=0,R[i]=i+1;
    for(int i=1;i<=n;++i)
        cin>>b[i],qb[i]=__gcd(qb[i-1],b[i]);
    int it,pre,u;
    a[n+1]=b[n+1]=fa[n+1]=fb[n+1]=0;
    for(int i=n;i>=1;--i)
    {
        it=i;
        fa[i]=__gcd(fa[i+1],a[i+1]),fb[i]=__gcd(fb[i+1],b[i+1]);
        while(it<=n)
            ga[it]=__gcd(ga[it],a[i]),gb[it]=__gcd(gb[it],b[i]),it=R[it];
        it=i+1,pre=i;
        while(it<n)
        {
            if(ga[it]==ga[R[it]]&&gb[it]==gb[R[it]]&&fa[it]==fa[R[it]]&&fb[it]==fb[R[it]])
                R[pre]=R[it],it=pre;
            pre=it,it=R[it];
        }
        pre=i-1,it=i;
        while(it<=n)
        {
            u=__gcd(qa[i-1],__gcd(gb[it],fa[it]))+__gcd(qb[i-1],__gcd(ga[it],fb[it]));
            if(u>ans)
                ans=u,cnt=it-pre;
            else if(u==ans)
                cnt+=it-pre;
            pre=it,it=R[it];
        }
    }
    cout<<ans<<' '<<cnt<<'\n';
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}