題意:

給一個數列,定義Magical GCD為序列gcd*序列length,問數列中子序列最大Magical GCD是多少.

解題思路:

定義i,j,i為長度,j去遍歷i之前的數,逐步求GCD更新最大值,這種做法的時間復雜度是 n^2,這樣暴力求肯定是超時的.

但是我們可以從這個思路去優化,我們會發現在逐步往前求GCD的時候,可能我們會連續的求出一些相同的GCD,這些相同的GCD,在下一次i+1往前求的時候,我們就不需要去和每個原數都求一遍GCD,我們只需要直接和這個(j到i的)GCD求一下GCD,就能求出j到i+1的GCD.所以對于連續相同的GCD我們只需要用一個變量來存儲,并存下最左邊的數的坐標,因為題目要求最大Magical GCD.所以i*i的遍歷就被改成i*(GCD個數),時間復雜度就下降了許多了.

代碼:

#include <cstdio>#include <iostream>#include <cstring>#include <bits/stdc++.h>#define LL long long using namespace std;const int maxn=1e5+5;LL a[maxn];struct p{   LL Gcd;   LL index;}g[maxn], gg[maxn];LL gcd(LL x, LL y){   if(x%y==0)return y;   else return gcd(y, x%y);}bool cmp(p a, p b){     return a.Gcd<b.Gcd;}int main(){   int t;   cin>>t;   int i, j;   int top=0;   while(t--)   {     int n;     scanf("%d", &n);     int i, j;     top=0;     LL ma=0;     for(i=0; i<n; i++)scanf("%lld", &a[i]);     for(i=0; i<n; i++)     {	int exi=0;	for(j=top; j>0; j--)	{	   if(g[j].Gcd==a[i])exi=1;	   g[j].Gcd=gcd(g[j].Gcd, a[i]);	   ma=max((i-g[j].index+1LL)*g[j].Gcd,ma);	  // PRintf(j==0?"%lld %lld/n":"%lld %lld+", g[j].Gcd, g[j].index);	}	if(exi==0)	{	   g[++top].Gcd=a[i];	   g[top].index=i;	   ma=max(ma, a[i]);	}	sort(g+1, g+top+1, cmp);	int k=1;	for(j=1; j<=top; j++)	{	   if(g[k].Gcd!=g[j].Gcd)	   {	     g[++k]=g[j]; //整個結構體賦值, 防止有內容忘記賦值 	   }	}	top=k;/*	for(j=1; j<=top; j++)	{	   printf("%lld+%d ", g[j].Gcd, j);	}	printf("/n");	*/     }     printf("%lld/n", ma);   }}