题解 P7009 [CERC2013] Magical GCD

Lynkcat · 2022-04-29 18:09:53 · 题解

关于这一类问题存在一个离线的预处理时间复杂度为 O(n \log v) 的解，但是我找到的大部分关于这个做法的解释都没有解释清楚复杂度。

我们从左往右枚举右端点 r，由于对于不同的左端点 l，最多只有 \log v 个本质不同的区间 gcd。维护一个二元 vector (l,v) 表示当前右端点为 r 的时候的左端点为 l 的 gcd 值为 v。考虑扩展 r\rightarrow r+1，我们发现会新增一个左端点 r+1，然后我们再次扫描所有二元组，把老的 v 和 a_{r+1} 取 gcd，相同的直接合并。

乍一看，这个做法的复杂度是 O(n \log^2 v) 的，因为要取 O(n\log v) 次 gcd。但是实际上我们发现每个左端点对复杂度的贡献最多为 \log，也就是说有效的取 gcd 递归层数不超过 O(2n \log v) 次，所以复杂度是 O(n\log v) 的。

// Lynkcat.
// Problem: P7009 [CERC2013] Magical GCD
// URL: https://www.luogu.com.cn/problem/P7009#submit
// Memory Limit: 1024 MB
// Time Limit: 8000 ms
// -----------------------------------------------
//The Hunting Party - Keys To The Kingdom
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define int ll
#define N 1000005
using namespace std;
inline char gc(){static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
// #define gc getchar
inline ll read(){char c=gc();ll su=0,f=1;for (;c<'0'||c>'9';c=gc()) if (c=='-') f=-1;for (;c>='0'&&c<='9';c=gc()) su=su*10+c-'0';return su*f;}
inline void write(ll x){if (x<0){putchar('-');write(-x);return;}if (x>=10) write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x),putchar(' ');}
inline void writeln(ll x){write(x);putchar('\n');}
int a[N],mx;
int n,q;
int b[N],ls[N],nx[N];
int ans;
void ers(int x)
{
    ls[nx[x]]=ls[x];
    nx[ls[x]]=nx[x];
}
void Bella()
{
    n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    nx[0]=n;
    ls[n]=0;
    b[n]=a[n];
    nx[n]=n+1;
    ans=a[n];
    for (int i=n-1;i>=1;i--)
    {
        int x=nx[0];
        b[i]=a[i];
        ls[i]=0;
        nx[i]=x;
        ls[x]=i;
        nx[0]=i;
        int now=i;
        while (now!=n+1)
        {
            b[now]=__gcd(a[i],b[now]);
            if (b[now]==b[ls[now]])
            {
                ers(ls[now]);
            }
            now=nx[now];
        }
        now=nx[0];
        int lst=i-1;
        int nowx=0;
        while (now!=n+1)
        {
            ans=max(ans,(now-i+1)*b[now]);
            lst=now;
            now=nx[now];
        }
    }
    writeln(ans);
}
signed main()
{
    int T=read();
    while (T--)
    {
        Bella();
    }
}
/*
*/