Magical GCD
The Magical GCD of a nonempty sequence of positive integers is defined as the product of its length
and the greatest common divisor of all its elements.
Given a sequence (a1, . . . , an), find the largest possible Magical GCD of its connected subsequence.
Input
The first line of input contains the number of test cases T. The descriptions of the test cases follow:
The description of each test case starts with a line containing a single integer n, 1 ≤ n ≤ 100000.
The next line contains the sequence a1, a2, . . . , an, 1 ≤ ai ≤ 1012
.
Output
For each test case output one line containing a single integer: the largest Magical GCD of a connected
subsequence of the input sequence.
Sample Input
1
5
30 60 20 20 20
Sample Output
80
题意：
给你N个数，求一个连续子序列，使得该序列中所有的最大公约数与序列长度的乘积最大
题解：
首先明确的做法是：枚举右端点，然后找到一个答案最大的左端点更新答案
那么如何找到这个最大的左端点,
假设我们求出了前i个数每个j(1<=j<=i) 的匹配的最优左端点，且gcd值，对应pos位置值已知，
那么我们可以根据gcd在非递增下，去更新这些gcd值和gcd值相同情况下 最左的左端点
这样的复杂度是nlogn的，
不同gcd至少相差2倍，我们就可以知道它是log的了
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5+, M = , mod = 1e9+, inf = 0x3f3f3f3f;
typedef long long ll;
//不同为1，相同为0 int T,n;
ll a[N];
ll gcd(ll a, ll b) { return b == ? a : gcd(b, a%b); }
vector<pair<ll,int > > v;
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
v.clear();
ll ans = ;
for(int i=;i<=n;i++) scanf("%lld",&a[i]);
for(int j=;j<=n;j++) {
v.push_back(make_pair(,j));
int k = v.size();
for(int i=;i<k;i++) {
v[i].first = (gcd(v[i].first,a[j]));
}
sort(v.begin(),v.end());
vector<pair<ll,int > > now;
for(int i=;i<v.size();i++) {
if(i == || v[i-].first != v[i].first) {
now.push_back(v[i]);
ans = max(ans, 1ll*v[i].first*(j - v[i].second+));
}
}
v = now;
}
cout<<ans<<endl;
}
return ;
}