自动搬运

查看原文

来自洛谷，原作者为

	Lynkcat Reset.

搬运于2025-08-24 22:25:50，当前版本为作者最后更新于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();
	}
}
/*
*/