题解【P7009 [CERC2013] Magical GCD】

传送门。

$\texttt{Description}$

给定长度为 $n$ 的正整数序列 $a$。

求 $\max_{1\le l\le r\le n}\{\gcd_{l\le j\le r}\{a_j\}\times (r-l+1)\}$。

$1\le n\le 10^5$，$1\le a_i\le 10^{12}$。

$\texttt{Solution}$

考虑 $\texttt{CDQ}$ 分治。

但问题在于 $\gcd$ 的值从左往右是单调不升的，$r-l+1$ 的值是上升的。没法快速维护这个东西。

然后聪明的你发现了 $\texttt{key conclusion}$：

一个前缀的 $\gcd$ 最多有 $\log$ 种取值。

简单证明一下：

右端点向右移动后，新的前缀 $\gcd$ 一定会变小，并且新的 $\gcd$ 会被原来的 $\gcd$ 整除，所以新的 $\gcd$ 一定不大于原来 $\gcd$ 的一半。

然后维护对于每一个值相同的前缀 $\gcd$，维护右边界即可。

代码：

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
inline ll read()
{
	ll s=0,w=1;
	char ch=getchar();
	while(ch<'0' or ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0' and ch<='9')s=s*10+(ch-'0'),ch=getchar();
	return s*w;
}
const int INF=1e9+10;
template
inline T Max(T x,T y){return x>y?x:y;}
inline int Min(int x,int y){return x0?x:-x;}
inline ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}
const int MAXN(1e5+10);
int n;
ll a[MAXN];
ll pre[MAXN],suf[MAXN];
int pos[MAXN];
inline ll CDQ(int l,int r)
{
	if(l==r) return a[l];
	int mid=(l+r)>>1,tot(0);
	ll ans=Max(CDQ(l,mid),CDQ(mid+1,r));
	suf[mid]=a[mid],pre[mid+1]=a[mid+1];
	for(register int i=mid-1;i>=l;i--) suf[i]=gcd(suf[i+1],a[i]);
	for(register int i=mid+2;i<=r;i++) pre[i]=gcd(pre[i-1],a[i]);
	for(register int i=mid+2;i<=r;i++)
		if(pre[i]!=pre[i-1]) pos[++tot]=i-1;
	pos[++tot]=r;
	for(register int i=l;i<=mid;i++)
		for(register int j=1;j<=tot;j++)
			ans=Max(ans,gcd(suf[i],pre[pos[j]])*1ll*(pos[j]-i+1));
	return ans;
}
inline void solve()
{
	scanf("%d",&n);
	for(register int i=1;i<=n;i++) a[i]=read();
	printf("%lld\n",CDQ(1,n));
	return;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--) solve();
}

$$\texttt{The End.by UF}$$