枚舉右端點,往前查找左端點….
右端點一定的話,最多只有log個不同的gcd值,
用一個數組記錄不同的GCD的值,對每個相同的GCD值記錄一下最靠左的位置…
因爲GCD值不是很多所以 移動右端點時暴力統計即可..
對與樣例:30 60 20 20 20
從第1個數座右端點開始枚舉 // (gcd,位置)
(30,1)
枚舉以第2個數做爲右端點
(30,1) (60,2)
第3個數
(10,1) (20,2)
….
後面幾個數都是一樣的…
第5個數
(10,1) (20,2)
這時 20*(5-2+1) = 80 最大
点击打开链接
1642 Magical GCDThe Magical GCD of a nonempty sequence of positive integers is defined as the product of its lengthand the greatest common divisor of all its elements.Given a sequence (a1, . . . , an), find the largest possible Magical GCD of its connected subsequence.InputThe 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.OutputFor each test case output one line containing a single integer: the largest Magical GCD of a connectedsubsequence of the input sequence.Sample Input1530 60 20 20 20Sample Output80
/* ***********************************************Author:CKbossCreated Time :2015年02月04日 星期三 13时12分27秒File Name:UVA1642.cpp************************************************ */#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>#include <cstdlib>#include <vector>#include <queue>#include <set>#include <map>using namespace std;typedef long long int LL;const int maxn = 101000;struct YUE{LL val,pos;};bool cmp(YUE a,YUE b){if(a.val!=b.val) return a.val<b.val;return a.pos<b.pos;}LL n;LL a[maxn];LL gcd(LL a,LL b){return (b)?gcd(b,a%b):a;}vector<YUE> yue,temp;int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int T_T;scanf("%d",&T_T);while(T_T–){yue.clear(); temp.clear();LL ans=0;scanf("%lld",&n);for(int i=0;i<n;i++){scanf("%lld",a+i);ans=max(ans,a[i]);}yue.push_back((YUE){a[0],0});for(int i=1;i<n;i++){int sz=yue.size();temp.clear();for(int j=0;j<sz;j++){LL g=gcd(a[i],yue[j].val);temp.push_back((YUE){g,yue[j].pos});}temp.push_back((YUE){a[i],i});sort(temp.begin(),temp.end(),cmp);yue.clear(); LL last=-1;for(int j=0,si=temp.size();j<si;j++){if(j==0){last = temp[j].val;yue.push_back(temp[j]);}else{if(last==temp[j].val) continue;else{last = temp[j].val;yue.push_back(temp[j]);}}}sz=yue.size();for(int j=0;j<sz;j++){ans=max(ans,yue[j].val*(i-yue[j].pos+1LL));}}printf("%lld\n",ans);}return 0;}
，命运如同手中的掌纹，无论多曲折，终掌握在自己手中。
