题目
对于一个由正整数组成的序列， Magical GCD 是指一个区间的长度乘以该区间内所有数字的最大公约数。给你一个序列，求出这个序列最大的 Magical GCD。
分析
根据暴力的思想，
\(枚举i，枚举j，a[j]=gcd(a[j],a[i])\)
答案就是\(max(a[j]*(i-j+1))\)
显然，当\(a[j]=a[j-1]\)的时候，\(a[j]\)就一定不会更新ans，所以，弄个双向链表，把\(a[j]\)踢掉。
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const int maxlongint=2147483647;
const int mo=1000000007;
const int N=100005;
using namespace std;
long long a[N],n,m,T,p,q,last[N],next[N],ans;
long long gcd(long long x,long long y)
{
if(x!=0) return gcd(y%x,x);
else return y;
}
int main()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld",&n);
next[0]=1;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
last[i]=i-1;
next[i]=i+1;
}
last[1]=next[n]=0;
ans=0;
for(int i=1;i<=n;i++)
for(int j=next[0];j<=i && j;j=next[j])
{
a[j]=gcd(a[j],a[i]);
ans=max(a[j]*(i-j+1),ans);
if(a[j]==a[last[j]])
{
next[last[j]]=next[j];
last[next[j]]=last[j];
}
}
printf("%lld\n",ans);
}
}