$MagicalGCD$Magical GCD

给一个长度为 $n(n\le 100000)$n(n≤100000) 的数列(每个数 $a\left[i\right]\le 10^{12}$a[i]≤1012 )，找到一个连续子序列使得子序列的公约数与长度的乘积最大，求这个最大值 .

$最初想法$最初想法

找规律发现好像 左端点固定, $gcd\ast 长度$gcd∗长度 随着 $长度$长度 增加而单调递增, 于是线段树查找区间和, $O\left(NlogN\right)$O(NlogN) 迎来 $50pts$50pts.
这是错的 . 早知道多打几组数据了 .

$正解部分$正解部分

若固定一个数的集合, 不断地往里面加数, 整个集合的 $gcd$gcd 只可能是 单调不增 的, 且每次减少都 至少减少为原来的 $\frac{1}{2}$21​ .

枚举右端点 $r$r, 左端点 $l$l从左向右移动, 可以发现 $gcd[l,r]$gcd[l,r] 是成块状连续的, 在 $gcd$gcd 相同的前提下, 显然取左端点最优,
所以对每个右端点, 只需用 双向链表 维护, 即可实现 只需枚举 $\log \left(a_i\right)$log(ai​) 个左端点 去更新答案 .

时间复杂度 $O(N\log (a_i\left)\right)$O(Nlog(ai​))

$实现部分$实现部分

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

const int maxn = 100005;

int N;
ll Ans;
ll A[maxn];
ll gcd[maxn];
int pre[maxn];
int nxt[maxn];

ll Gcd(ll a, ll b){ return !b?a:Gcd(b, a%b); }

void Work(){
        Ans = 0;
        scanf("%d", &N);
        for(reg int i = 1; i <= N; i ++){
                scanf("%lld", &A[i]);
                pre[i] = i-1, nxt[i] = i+1;
                gcd[i] = A[i];
        }
        nxt[0] = 1;
        for(reg int i = 1; i <= N; i ++)
                for(reg int j = nxt[0]; j <= i; j = nxt[j]){
                        int &pre_1 = pre[j], &pre_2 = pre[pre_1];
                        gcd[j] = Gcd(gcd[j], A[i]);
                        if(gcd[j] == gcd[pre_1]){
                                nxt[pre_2] = j;
                                pre[j] = pre_2;
                        }
                        Ans = std::max(Ans, 1ll*(i-pre_1)*gcd[j]);
                }
        printf("%lld\n", Ans);
}

int main(){
        int T;
        scanf("%d", &T);
        while(T --) Work();
        return 0;
}