Time Limits: 2000 ms Memory Limits: 131072 KB
Description
对于一个由正整数组成的序列， Magical GCD 是指一个区间的长度乘以该区间内所有数字的最大公约数。给你一个序列，求出这个序列最大的 Magical GCD。
Input
单个测试点包含多组数据。 输入的第一行是一个整数T表示数据组数。 每组数据的第一行是一个整数N，描述序列长度。 接下来N个数字，描述这个序列元素A[i]。
Output
对于每组测试数据输出一行，包含一个整数，表示序列最大的 Magical GCD。
Sample Input
1 5 30 60 20 20 20
Sample Output
80
Data Constraint
对于 30%分值的数据，N <= 10，T <= 11,000, A[i] <= 100 对于剩余 70%分值的数据，N <= 100,000，T <= 20, A[i] <= 10^12 C/C++选手读入和输出 64 位整数请使用%lld。
Hint
【样例说明】 对于子区间 60 20 20 20，长度为 4，最大公约数为 20，此段 Magical GCD 为 80.
【评分标准】 对于每个测试点，你的输出必须和标准输出一致得到全部分数，否则不得分。
Solution
不难发现，固定了左端点后，右端点往右移GCD是单调不增的考虑枚举右端点
i
i
i ，
b
[
j
]
b[j]
b[j] 表示区间
[
j
,
i
]
[j,i]
[j,i] 的GCD我们发现对于
b
[
j
]
=
=
b
[
j
−
1
]
b[j]==b[j-1]
b[j]==b[j−1] ，我们只需要保留
j
−
1
j-1
j−1 ，而不需要
j
j
j ，为什么呢？既然
b
[
j
]
=
=
b
[
j
−
1
]
b[j]==b[j-1]
b[j]==b[j−1] ，那么当右端点继续右移时，他们的到右端点的GCD是一样的而
j
−
1
j-1
j−1 的长度显然更优，那么
j
j
j 就没有存在的必要，我们用链表维护一下，跳过不必要的区间就好了
如果我的表述不清楚，可以看这个
Code
#include<algorithm>
#include<cstdio>
using namespace std
;
const int N
=1e5+5;
int T
,n
,l
[N
],r
[N
];
long long ans
,a
[N
],b
[N
];
long long gcd(long x
,long y
)
{
return y
?gcd(y
,x
%y
):x
;
}
int main()
{
freopen("magical.in","r",stdin);
freopen("magical.out","w",stdout);
scanf("%d",&T
);
while(T
--)
{
scanf("%d",&n
),ans
=0;
for(int i
=1;i
<=n
;++i
)
{
scanf("%lld",&a
[i
]),b
[i
]=a
[i
];
l
[i
]=i
-1,r
[i
]=i
+1;
}
for(int i
=1;i
<=n
;++i
)
for(int j
=1;j
<=i
;j
=r
[j
])
{
b
[j
]=gcd(b
[j
],a
[i
]);
ans
=max(ans
,b
[j
]*(i
-j
+1));
if(b
[j
]==b
[j
-1]) r
[l
[j
]]=r
[j
],l
[r
[j
]]=l
[j
];
}
printf("%lld\n",ans
);
}
}
