UVA 1642 Magical GCD（gcd的性质，递推）

分析：对于区间[i,j]，枚举j。

固定j以后，剩下的要比较M_gcd(k,j) = gcd(ak,...,aj)*(j-k+1)的大小, i≤k≤j。

此时M_gcd(k,j)可以看成一个二元组(g, k)。

根据gcd的性质gcd(a1,a2,...,an) = gcd(a1,gcd(a2,..,an))，而且gcd(a,b) | b。

如果gcd(ak,...,aj) != gcd(ak+1,...,aj)，那么gcd(ak,...,aj) ≤ 2*gcd(ak+1,...,aj)。

原本有j个gcd，而不同的gcd值之间至少相差2倍，所以不同的gcd值的数量是O(log₂j)。

gcd相同的只要保留最小的k。

把j-1对应的M_gcd的二元组保留成一个表tb。然后想想怎么递推j的表，

根据gcd(a1,a2,...,aj) = gcd(gcd(a1,..aj-1),aj)，一部分是tb_j.g =  gcd(tb_j-1.g,a[j])，下标没有改变，

另一部分是二元组(a[j],j)。一个有序序列依次和a[j]求gcd以后不一定有序了，去重复前还要排下序。

总的复杂度是O(nlogn*loglogn )

/*********************************************************
*      --------------Crispr---------------               *
*   author AbyssalFish                                   *
**********************************************************/
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
//list<ll> gcd_tab;
//ll g_tb[64];
//int idx[64];
typedef pair<ll,int> pli;
pli tb[64];

int sz;

ll gcd(ll a,ll b)
{
    ll t;
    while(b){
        t = b;
        b = a%b;
        a = t;
    }
    return a;
}


//#define LOCAL
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    int T , n;
    scanf("%d",&T);
    ll a;
    while(T--){
        scanf("%d",&n);
        sz = 0;
        ll ans = 0;

        #define val first
        #define idx second
        for(int i = 0; i < n; i++){
            scanf("%lld",&a);
            for(int j = 0; j < sz; j++){
                tb[j].val = gcd(tb[j].val,a);
            }
            tb[sz++] = pli(a,i-1);
            sort(tb,tb+sz);
            int k = 0;
            for(int j = 1; j < sz; j++){
                if(tb[j].val != tb[k].val){
                    ans = max((i-tb[k].idx)*tb[k].val, ans);
                    if(++k != j) tb[k] = tb[j];
                }
            }
            ans = max((i-tb[k].idx)*tb[k].val, ans);
            sz = k+1;
        }
        printf("%lld
", ans);
    }
    return 0;
}