Also available: UVALive 6582, UVA 1642, Gym 100299C

题意

给定一个序列，定义一个连续子序列的 Magical GCD 为子序列内所有元素的 GCD 乘上区间长度，求最大的 Magical GCD。

解题思路

首先我们可以想到枚举区间右端点，对于每一个右端点，向左遍历来不断更新最大值，不过这样的时间复杂度会到 $O(n^{2})$，对于这道题是撑不住的，因此我们需要想办法在每次枚举右端点时，降低遍历左端点时的时间复杂度。

我们可以注意到，在确定右端点的所有区间内，随着区间长度不断增大，GCD 只会保持不变或者减小，且如果减小，新的 GCD 最大为原来的 1/2（当从因子中拿出的数最小，新 GCD 最大，拿出的最小为 2）。由此可知，对于区间内最大数值 m，不同 GCD 的个数最大为 $\log_2 m$，这样我们每次只需要遍历所有不同的 GCD，复杂度降低到 $O(n\log m)$。对于相同的 GCD，我们只需要记录最左端的一个即可（为了取最大长度）。

因此，本题的做法就很清楚了，只需要枚举右端点，然后维护一个记录不同 GCD 及其最左端位置的数据结构并不断更新答案即可。

示例解释（i 为枚举的右端点，括号内为维护的不同 GCD 值及其最左端位置）：

i = 0
(30, 0)

i = 1
(30, 0)
(60, 1)

i = 2
(10, 0)
(20, 1)

i = 3
(10, 0)
(20, 1)

i = 4
(10, 0)
(20, 1)

参考代码

#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;

long long GCD(long long a, long long b) {
    return b ? GCD(b, a%b) : a;
}

int main(int argc, char const *argv[]) {
    int t, n;
    long long a[100000];
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i=0; i<n; ++i) {
            scanf("%lld", &a[i]);
        }
        long long ans = a[0];
        stack<pair<long long, int> > s; // 维护不同 GCD 的值及其最左端位置
        s.push(make_pair(a[0], 0));
        for(int i=1; i<n; ++i) {
            vector<pair<long long, int> > v;
            v.push_back(make_pair(a[i], i));
            while(!s.empty()) {
                v.push_back(make_pair(GCD(s.top().first, a[i]), s.top().second)); // 获得栈顶的 GCD 并计算新的 GCD，暂存到 v 中
                s.pop();
            }
            for(int j=1; j<v.size(); ++j) { // 去除重复的 GCD 值
                if(v[j].first == v[j-1].first)
                    v.erase(v.begin()+(j--)-1);
            }
            for(int j=v.size()-1; j>=0; --j) { // 将新的一组不同 GCD 值重新放回栈内并更新答案
                ans = max(ans, v[j].first*(i-v[j].second+1));
                s.push(v[j]);
            }
        }
        printf("%lld\n", ans);
    }
    
    return 0;
}