以一个数字开头的子序列的gcd种类不会超过logn种，因此去找相同gcd最长的位置，更新一下答案，复杂度O(nlogn^2)

1 #include
     
       2 #include
      
        3 #include
       
         4 #define N 300010 5 using namespace std; 6 int n,i,Log[N],j,l,left,right,mid; 7 long long s[N][20],ans; 8 long long gcd(long long a,long long b) 9 {10     if (b==0) return a;11     return gcd(b,a%b);12 }13 long long Q(int l,int r)14 {15     int k=Log[r-l+1];16     return gcd(s[l][k],s[r-(1<
        
         =1;i--)31     for (j=1;j<=Log[n];j++)32     s[i][j]=gcd(s[i][j-1],s[i+(1<<(j-1))][j-1]);33     34     for (i=1;i<=n;i++)35     {36         l=i;37         while (l<=n)38         {39             left=l;40             right=n;41             while (left<=right)42             {43                 mid=(left+right)>>1;44                 if (Q(i,mid)==Q(i,l))45                 left=mid+1;46                 else47                 right=mid-1;48             }49             l=right+1;50             ans=max(ans,(right-i+1)*Q(i,right));51         }52     }53     printf("%lld\n",ans);54     }55 }