分析：对于区间[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(log2j)。
gcd相同的只要保留最小的k。
把j-1对应的M_gcd的二元组保留成一个表tb。然后想想怎么递推j的表，
根据gcd(a1,a2,...,aj) = gcd(gcd(a1,..aj-1),aj)，一部分是tbj.g = gcd(tbj-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\n", ans); } return 0; }
原文：http://www.cnblogs.com/jerryRey/p/4964501.html